Sieb-des-Eratosthenes-Generator (Kostenlos) – Primzahlenliste & N-te Primzahl
Geben Sie eine Obergrenze N ein, um mit dem Sieb des Eratosthenes eine Primzahlenliste zu erzeugen, Schritt für Schritt visualisiert. Finden Sie außerdem die N-te Primzahl (bis zur 1.000.000.) — kostenlos, im Browser, ohne Anmeldung.
Sieb des Eratosthenes für 1–100 (Übersichtstabelle)
Grüne Zellen sind Primzahlen; die übrigen wurden vom Sieb ausgeschlossen.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
| 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |
| 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 |
| 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 |
| 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 |
| 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 |
| 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 |
| 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 |
| 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 |
1 ist weder prim noch zusammengesetzt und bleibt daher ungefärbt.
Was das Sieb des Eratosthenes leistet
Das Sieb des Eratosthenes ist das klassische Verfahren zum Auffinden von Primzahlen, benannt nach dem griechischen Gelehrten des 3. Jahrhunderts v. Chr. Der Einfall ist verblüffend schlicht: Nehmen Sie der Reihe nach jede Zahl ab zwei, erklären Sie sie zur Primzahl, sofern sie noch nicht gestrichen wurde, und streichen Sie anschließend alle ihre Vielfachen. Streichen Sie die Vielfachen von zwei, dann die der übrig gebliebenen drei, dann die der fünf – wiederholen Sie das bis zur Quadratwurzel Ihrer Obergrenze, und jede noch stehende Zahl ist prim.
Geben Sie diesem Werkzeug eine Obergrenze, und es erzeugt die Liste der Primzahlen bis eine Million. Es zeigt den Streichvorgang Schritt für Schritt, sodass Sie mit eigenen Augen verfolgen können, welche Primzahl welche Zahlen entfernt hat. Es arbeitet auch rückwärts und beantwortet die Frage «Welches ist die N-te Primzahl?» bis hin zur millionsten Stelle. Alles wird in Ihrem Browser berechnet, sodass nichts von dem, was Sie eingeben, ihn verlässt.
So erzeugen Sie eine Primzahlliste
- Geben Sie die Obergrenze N ein Nennen Sie eine ganze Zahl zwischen 2 und 1.000.000. Mit etwas Kleinem wie 100 zu beginnen, macht die Mechanik des Siebs weit besser sichtbar.
- Prüfen Sie Anzahl und größte Primzahl Sie erfahren, wie viele Primzahlen bis N liegen – geschrieben π(N) – und welche die größte davon ist.
- Verfolgen Sie die Streichschritte Bei kleineren Grenzen zeigt jede Stufe, welche Primzahl verwendet wurde und welche Zahlen sie entfernt hat.
- Schlagen Sie die N-te Primzahl nach Geben Sie eine Position ein, und das Werkzeug liefert die Primzahl, die sie einnimmt.
Tipps für die Nutzung
- Das Sieb des Eratosthenes listet effizient alle Primzahlen bis N auf, indem es die Vielfachen jeder gefundenen Primzahl ausgehend von 2 durchstreicht.
- Setzen Sie die Obergrenze N auf 400 oder weniger, um Schritt für Schritt genau zu sehen, welche Primzahl welche Zahl eliminiert hat.
- Die N-te-Primzahl-Suche unterstützt Anfragen wie „Was ist die 1.000.000. Primzahl", nützlich um die Existenz sehr großer Primzahlen zu bestätigen.
- Alles läuft lokal in Ihrem Browser — die erzeugte Primzahlenliste wird nie an einen Server gesendet.
Wofür sich das eignet
Algorithmen lernen
Das Sieb ist das Lehrbuchbeispiel für die Komplexität O(n log log n), und beim Zusehen prägt sich der Gedanke ein.
Die eigene Umsetzung überprüfen
Vergleichen Sie die Ausgabe eines selbst geschriebenen Siebs damit, um die richtige Folge zu bestätigen.
Die Verteilung der Primzahlen beobachten
Verändert man die Grenze und betrachtet das Wachstum von π(N), bekommt man ein Gefühl für den Primzahlsatz und sein ungefähres Verhalten N / log N.
Sich in die Kryptographie einlesen
Public-Key-Verfahren wie RSA beruhen auf großen Primzahlen; hier lässt sich erfassen, wie dicht Primzahlen auftreten.
Begriffe zu Primzahlen und Sieben
- Primzahl
- Eine natürliche Zahl ab zwei, deren einzige positive Teiler eins und sie selbst sind. Die Eins zählt nicht als Primzahl.
- Zusammengesetzte Zahl
- Eine natürliche Zahl ab zwei, die nicht prim ist. Genau diese Zahlen streicht das Sieb.
- π(N)
- Die Funktion, die angibt, wie viele Primzahlen bis N liegen; sie heißt Primzahlzählfunktion.
- Streichen
- Das Markieren der Vielfachen einer Primzahl, um sie aus den Kandidaten zu entfernen. Dieser Vorgang gab dem Verfahren seinen Namen.
- Warum die Quadratwurzel genügt
- Jedes Vielfache einer Primzahl oberhalb der Quadratwurzel von N wurde bereits als Vielfaches einer kleineren Primzahl gestrichen.
- Primzahlsatz
- Die Aussage, dass π(N) asymptotisch zu N / log N verläuft; sie beschreibt, wie rasch Primzahlen seltener werden.
Häufige Fragen
Übrigens – Warum ein 2000 Jahre alter Algorithmus noch immer genutzt wird
Das Sieb des Eratosthenes ist einer der ältesten erhaltenen Primzahlgeneratoren, der dem antiken griechischen Gelehrten Eratosthenes zugeschrieben wird, der im 3. Jahrhundert v. Chr. Chefbibliothekar der Bibliothek von Alexandria war. Dass eine vor über zweitausend Jahren ersonnene Methode heute noch in Informatikkursen gelehrt wird, zeugt von ihrer eleganten Einfachheit.
Der Mechanismus ist verblüffend einfach: Man listet die ganzen Zahlen ab 2 auf, betrachtet die kleinste noch nicht markierte Zahl als Primzahl und streicht alle ihre Vielfachen durch. Wiederholt man dies bis √N, sind alle Primzahlen bis N gefunden. Um eine vollständige Primzahlenliste zu erzeugen, ist dies weit effizienter, als jede Zahl einzeln per Probedivision zu testen.
Die Suche nach riesigen Primzahlen geht bis heute weiter — verteilte Rechenprojekte wie GIMPS (die Great Internet Mersenne Prime Search) entdecken weiterhin Mersenne-Primzahlen mit zig Millionen Stellen. Das Sieb selbst wird nicht genutzt, um so große Primzahlen zu finden, aber seine Kernidee — Vielfache mechanisch auszuschließen — bildet die Grundlage fortgeschrittenerer Primzahltests.