Primzahlsieb & Ulam-Spirale

Beobachte, wie das Sieb des Eratosthenes zusammengesetzte Zahlen aussiebt, oder sieh Primzahlen auf einer Ulam-Spirale.

Rechenbeispiel — Primzahlsieb & Ulam-Spirale

π(100)	25 Primzahlen
N / ln N	21.7(13.1% Fehler)
Li(N)	29.1(16.3% Fehler)
Zwillingspaare	8 Paare
Größte Lücke	8

Das sind die Werte, die der Rechner beim Öffnen der Seite anzeigt. Ändere oben eine Eingabe, um sie neu zu berechnen.

Interaktive Simulation wird geladen...

Lektion

Die Theorie — Primzahlsieb & Ulam-Spirale

Das Feld druckt zwei verschiedene Arten von Zahl, und es lohnt sich, sie zu trennen, bevor man irgendetwas anderes liest. π(N) ist eine Anzahl — wie viele Primzahlen das Sieb tatsächlich stehen ließ, 25 bei N = 100 und 95 bei N = 500, exakt und nicht gerundet. Die beiden Zeilen darunter sind Schätzungen ebendieser Anzahl. Der Primzahlsatz behauptet, dass eine von ihnen im Grenzwert das Verhältnis richtig trifft; er behauptet nicht, dass sie die Zahl richtig trifft. Das sind sehr verschiedene Versprechen, und in der Fehlerspalte wird der Unterschied sichtbar.

Was die einzelnen Symbole bedeuten

N: die Obergrenze, bis zu der gesiebt wird, und die einzige Eingabe. Der Regler reicht bis 10000.
π(N): die Anzahl der Primzahlen, die N nicht überschreiten. Gezählt, nicht geschätzt — es sind schlicht so viele Felder, wie das Sieb nicht durchgestrichen hat.
N / ln N: die einfachste Schätzung dieser Anzahl. Bei jedem N, das dieser Regler erreicht, liegt sie unter der Wahrheit.
Li(N): das Integrallogarithmus ∫₂ᴺ dt/ln t, eine schärfere Schätzung. Bei jedem N, das dieser Regler erreicht, liegt sie über der Wahrheit.

Woher die Formel kommt

Das Sieb fragt nie, ob eine Zahl prim ist. Es beginnt bei 2, streicht jedes Vielfache von 2, geht zur nächsten noch stehenden Zahl, streicht jedes Vielfache davon und wiederholt das. Primalität wird nicht geprüft; sie ist das, was übrig bleibt.
Man muss nur Vielfache von Primzahlen bis √N streichen. Ist eine Zahl n ≤ N zusammengesetzt, so ist n = a·b mit a ≤ b, also a ≤ √n ≤ √N — jede zusammengesetzte Zahl hat einen Teiler höchstens in Höhe der Wurzel und wurde daher schon gestrichen, als dieser Teiler an der Reihe war. Bis 100 zu sieben braucht nur die Durchgänge für 2, 3, 5 und 7.
Zähle die Überlebenden, und du hast π(N) exakt. Deshalb ist die oberste Zeile eine Tatsache und die beiden darunter sind Meinungen: das Sieb liefert die Anzahl als Nebenprodukt seines Durchlaufs.
Nun vergleiche. Der Primzahlsatz sagt π(N) · ln N / N → 1 für wachsendes N. Beachte, was er nicht sagt: ein gegen 1 strebendes Verhältnis erlaubt es dem prozentualen Fehler, sehr lange groß zu bleiben — und die nächste Zeile zeigt genau das.

So liest du, was du siehst

Lies die beiden Fehlerwerte als Wettrennen und verändere N. Bei N = 100 führt die grobe Schätzung: 13.1% gegen Lis 16.3%. Gehe auf N = 200, und es kehrt sich um — 17.9% gegen 6.9% — und es kehrt sich nie wieder zurück. Das eigentlich Bemerkenswerte ist aber, was N/ln N nicht tut. Über zwei Größenordnungen lautet sein Fehler 14.8%, 13.1%, 15.3%, 13.8%, 12.2%: er schwankt und verbessert sich kaum. Li geht über dieselbe Spanne von 16.3% auf 2.8%. Beide Schätzungen erfüllen den Primzahlsatz; nur eine davon taugt in den Größenordnungen, die du sehen kannst. Ebenso beständig sind die Vorzeichen — N/ln N liegt hier bei jedem N unter der Anzahl, Li über ihr.

Setzt voraus: Dass N klein genug ist, um vollständig gesiebt zu werden: die Anzahl ist exakt, weil jede Zahl bis N tatsächlich vorgehalten und gestrichen wird — deshalb endet die Obergrenze bei 10000 und nicht bei 10¹⁰. Die Fehlerprozente beziehen sich auf π(N), messen also die Schätzungen und nie die Anzahl.
Versagt, wenn: Li(N) > π(N) gilt bei jedem N, das diese Seite erreichen kann, und sieht damit aus wie ein Gesetz. Es ist keines. Littlewood bewies 1914, dass die Differenz unendlich oft das Vorzeichen wechselt, es also N gibt, bei denen Li zu wenig zählt — und im Jahrhundert seither hat niemand auch nur ein einziges vorgezeigt. Bays und Hudson drückten den ersten Wechsel 1999 unter etwa 1.4×10³¹⁶, und enger ist er seither nicht geworden. Diese Seite zeigt dir also ein Muster, das nachweislich nicht allgemein gilt, und keine Reglerstellung erreicht das Gegenbeispiel. Diese Lücke zwischen dem Sichtbaren und dem Wahren ist die ehrliche Gestalt dieses Themas.

Das Ausdünnen, das du im Raster siehst, ist der Teil, den niemand beweisen kann 🖖

Die genaue Verteilung der Primzahlen wird durch die Nullstellen der Riemannschen Zetafunktion ζ(s) bestimmt. Alle 10¹³ bekannten nicht-trivialen Nullstellen liegen auf der kritischen Geraden Re(s) = 1/2. Ein Beweis dafür für alle Nullstellen würde die schärfstmöglichen Schranken für die Primzahlzählfunktion liefern — und ein Preisgeld von 1 Million Dollar (Millennium-Preis) einbringen. Stand 2025 ist sie unbewiesen.

Sieben statt prüfen 🖖

Das Sieb des Eratosthenes findet Primzahlen durch Ausschluss, nicht durch Einzelprüfung. Beginne bei 2, streiche jedes Vielfache, springe zur nächsten überlebenden Zahl und wiederhole; was nie gestrichen wird, ist prim. Der clevere Kniff: Um alle Zahlen bis n zu sieben, musst du nur Vielfache der Primzahlen bis √n entfernen. Für alles unter 100 genügt es also, Vielfache von 2, 3, 5 und 7 zu streichen.

Ulams gelangweiltes Gekritzel 🖖

1963 kritzelte der Mathematiker Stanisław Ulam aus Langeweile während eines Vortrags die ganzen Zahlen in eine quadratische Spirale und markierte die Primzahlen — verblüffend klare diagonale Streifen tauchten auf. Diese Diagonalen folgen primzahlreichen quadratischen Formeln wie Eulers n² + n + 41, die für jedes n von 0 bis 39 eine Primzahl liefert. Warum manche Diagonalen so dicht bleiben, ist bis heute nicht vollständig verstanden.

Aufgaben vollständig gelöst

Sieben der 25 Primzahlen unter 100 von Hand 5 Schritte
Es gibt 25 Primzahlen unter 100. Sieben Sie sie von Hand aus — das macht weniger Arbeit, als man vermuten würde — und testen Sie dann den Primzahlsatz an einer Stichprobe, die weit zu klein für ihn ist.
1. Die Ersparnis des Siebs ist der Grund, warum es einen eigenen Namen verdient. Wenn n ≤ 100 zusammengesetzt ist, zerfällt es als ab, und der kleinere Faktor kann √100 = 10 nicht überschreiten. Das Streichen der Vielfachen jeder Primzahl bis 10 entfernt somit jede zusammengesetzte Zahl: Vier Primzahlen erledigen die gesamte Aufgabe.
  
  $n \leq 100 composite ⟹ n = ab with min (a, b) \leq 100 = 10$
2. Streichen Sie die Vielfachen von 2, 3, 5 und 7, jeweils beginnend bei deren Quadrat, da alles darunter bereits gestrichen ist. Fünfundzwanzig Zahlen bleiben übrig.
  
  $strike multiples of 2, 3, 5, 7 from 4 upward ⟹ π (100) = 25$
3. Der Primzahlsatz besagt, dass die Anzahl asymptotisch N/ln N beträgt. Bei N = 100 ist das 21,7.
  
  $π (N) \sim \frac{N}{ln N} : \frac{100}{ln 100} = \frac{100}{4.6052} = 21.7$
4. Das ist um 13 % zu niedrig, was ein asymptotisches Ergebnis bei 100 durchaus sein darf. Umgekehrt gelesen ist es hier dennoch nützlich: Die Dichte der Primzahlen nahe N ist 1/ln N, sodass etwa 22 % der Zahlen nahe 100 Primzahlen sind, gegenüber 7,2 % nahe einer Million. Primzahlen dünnen sich logarithmisch aus, was in der Tat sehr langsam geschieht.
  
  $\frac{25 - 21.7}{25} = 13.1%, \frac{1}{ln 100} = 21.7% vs \frac{1}{ln 1 0 ^{6}} = 7.2%$
5. Die Lücken stimmen überein. Die mittlere Lücke unter 100 beträgt 100/25 = 4, und die größte ist 8 — die Folge von 89 bis 97. Das Doppelte des Durchschnitts und nicht schlechter.
  
  $mean gap = \frac{100}{25} = 4, largest = 97 - 89 = 8$
Antwort

Das Sieb liefert π(100) = 25 und das Werkzeug gibt den Schätzwert mit 21,7 an, 13,1 % zu niedrig. Dieser Fehler ist kein Versagen des Satzes; er macht die Konvergenzgeschwindigkeit des Satzes sichtbar, und diese Konvergenz ist bekanntermaßen uneilig — erhöht man N auf 10 000, um vier Größenordnungen nach oben, liegt die Schätzung immer noch im zweistelligen Bereich zu niedrig. Was auf jeder Skala gilt, ist die Aussage über die Dichte. Eine Zahl von 4,6 nahe 100 ist prim, eine von 13,8 nahe einer Million, und weil der Logarithmus so langsam wächst, gehen die Primzahlen nie aus und werden nicht einmal wirklich selten.

$π (100) = 25 from four primes; \frac{N}{ln N} = 21.7 (13.1% low)$
Die offensichtliche Schätzung für 8 Zwillingspaare unter 100 6 Schritte
Die Tafel zählt 25 Primzahlen unter 100 und 8 Primzahlzwillinge. Für die erste Zahl gibt es eine berühmte Schätzung, die auf 13 % herankommt. Versuche die naheliegende Schätzung für die zweite — und sieh zu, wie sie um einen Faktor danebenliegt, der einen Namen hat.
1. Nimm die gedruckte Anzahl und die gedruckte Schätzung als Ausgangspunkt: nahe N ist eine Zahl mit etwa 1/ln N Wahrscheinlichkeit prim, bei N = 100 also rund 0,2171.
  
  $π (100) = 25, \frac{N}{ln N} = \frac{100}{4.6052} = 21.7$
2. Nun nimm an, n und n+2 seien unabhängig. Ist jede mit Wahrscheinlichkeit 1/ln N prim, so sind es beide mit dem Quadrat davon.
  
  $P_{1} \approx \frac{1}{ln N} = 0.2171 ⟹ P_{2} \approx P_{1}^{2} = \frac{1}{( ln N ) ^{2}}$
3. Multipliziere mit N und vergleiche mit dem Werkzeug. Die Schätzung sagt 4,72 Zwillingspaare unter 100; das Sieb fand 8. Das ist nicht knapp daneben — das sind 40 % zu wenig.
  
  $N P_{2} = \frac{100}{21.208} = 4.72 ⟷ π_{2} (100) = 8$
4. Die Unabhängigkeit ist der falsche Schritt, und eine einzige Primzahl zeigt warum. Nimm eine ungerade Primzahl p: ein zufälliges n wird von p in einem von p Fällen erschlagen, das Paar aber immer dann, wenn n oder n+2 durch p teilbar ist — zwei Reste von p. Die Überlebensrate ist also (p−2)/p und nicht das Quadrat von (p−1)/p, das die Unabhängigkeit unterstellt.
  
  $p > 2 : n \equiv 0 \lor n + 2 \equiv 0 (mod p) ⟹ \frac{p - 2}{p} \neq = (\frac{p - 1}{p})^{2}$
5. Multipliziere diese Korrektur über alle ungeraden Primzahlen, und sie konvergiert gegen eine Konstante. Verdoppelt ist sie 1,3203, und angewandt hebt sie die Schätzung auf 6,23.
  
  $2 C_{2} = 2 p > 2 \prod \frac{p ( p - 2 )}{( p - 1 ) ^{2}} = 1.3203 ⟹ 1.3203 \times 4.72 = 6.23$
6. Bei N = 100 immer noch zu wenig gegenüber 8 — die Schätzung ist asymptotisch, und 100 ist eine kleine Zahl. Sie konvergiert: 156 Paare unter 10⁴, 6917 unter 10⁶.
  
  $N = 1 0^{4} : 156 N = 1 0^{6} : 6917$
Antwort

Die naive Zahl ist 4,72, die korrigierte 6,23, und die Wahrheit ist 8 — und der Korrekturfaktor 1,3203 ist ein unendliches Produkt über die Primzahlen. Diese Konstante ist der Preis dafür, Unabhängigkeit anzunehmen, wo keine herrscht, und sie hat die Gestalt fast jeder schweren Frage des Fachs: die Primzahlen sind zufällig genug, dass eine Heuristik funktioniert, und strukturiert genug, dass sie eine Korrektur braucht, die niemand von Grund auf herleiten kann. Die Primzahlzwillingsvermutung besagt, dass dieser Schätzung nie die Paare ausgehen, und sie ist bis heute offen.

$π_{2} (N) \sim 2 C_{2} \frac{N}{( ln N ) ^{2}}, 2 C_{2} = 1.3203 : 4.72 \to 6.23 ⟷ 8$

Quellen (4)

Why the page’s most convincing pattern is not a law — the difference changes sign infinitely often: J. E. Littlewood, "Sur la distribution des nombres premiers." Comptes Rendus de l’Académie des Sciences, Paris 158, 1869–1872, 1914. No DOI: the volume predates them.
How far the first sign change has been pinned down, and where the 1.4×10³¹⁶ comes from: C. Bays & R. H. Hudson, "A new bound for the smallest x with π(x) > li(x)." Mathematics of Computation 69, 1285–1296, 1999.
How far the Riemann hypothesis has actually been verified — note this is a bound on height, a different measure from a count of zeros: D. J. Platt & T. S. Trudgian, "The Riemann hypothesis is true up to 3·10^12." Bulletin of the London Mathematical Society 53, 792–797, 2021.
The prize, and its official problem statement: Clay Mathematics Institute, Millennium Prize Problems — the Riemann Hypothesis.

Vom 42Math-Team · Aktualisiert 2026-06-20

Anhand veröffentlichter Quellen geprüft. Korrekturen willkommen. Redaktionsrichtlinie · Korrekturen

Alle Lektionen: Mathematik →

Beispielaufgaben

Klein (100) - Siebe bis 100, und die grobe Schätzung gewinnt: N/ln N liefert 21,7 bei 13,1 % Abweichung, während Li(100) = 29,1 um 16,3 % abweicht. Das ist die einzige Voreinstellung, bei der das passiert. Gehst du auf 500, fällt der Fehler von Li auf 6,2 %, während N/ln N bei 15,3 % stehenbleibt.
Mittel (500) - 95 Primzahlen unter 500, in 24 Zwillingspaaren. Die größte Lücke beträgt 14 – jene Spanne von 113 bis 127, die ganz ohne Primzahlen bleibt. Dieser Rekord hält dann bis 523, wo sich ein Abstand von 18 auftut. Eine Rekordlücke wächst nicht stetig mit N. Sie wartet ab.
Kühle Spalten - 154 Primzahlen unter 900, in 35 Zwillingspaaren. Gehst du weiter bis 1000, findest du 14 weitere Primzahlen, aber kein einziges neues Zwillingspaar: Das letzte bilden 881 und 883. Zwillinge dünnen schneller aus als die Primzahlen selbst. Ob sie jemals enden, ist bis heute ungelöst.
Ulam 400 - Dieselben 78 Primzahlen wie im Gittermodus, neu angeordnet auf einer quadratischen Spirale. An den Zahlen selbst hat sich nichts verändert. Die diagonalen Bänder entstehen allein dadurch, wo die Spirale die einzelnen ganzen Zahlen platziert. Deshalb kann ein Bild Muster andeuten, die die Arithmetik bisher nicht bestätigt hat.
Primzahlsatz (1000) - π(1000) = 168. N/ln N liefert 144,8 und weicht damit um 13,8 % ab; Li(1000) ergibt 177,0 bei einer Abweichung von 5,3 %. Beide erfüllen den Primzahlsatz. Doch für jedes N, das dieses Werkzeug erreicht, ist nur eine der beiden brauchbar – und Li liegt dabei jedes einzelne Mal über der tatsächlichen Anzahl.