Sieb-des-Eratosthenes-Generator (Kostenlos) – Primzahlenliste & N-te Primzahl

Gib eine Obergrenze N ein, um mit dem Sieb des Eratosthenes eine Primzahlenliste zu erzeugen, Schritt für Schritt visualisiert. Finde 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.

Tipps

  • Das Sieb des Eratosthenes listet effizient alle Primzahlen bis N auf, indem es die Vielfachen jeder gefundenen Primzahl ausgehend von 2 durchstreicht.
  • Setze 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 deinem Browser — die erzeugte Primzahlenliste wird nie an einen Server gesendet.

Häufige Fragen

Es ist ein Verfahren zur Primzahlauflistung, das dem Mathematiker Eratosthenes aus dem 3. Jahrhundert v. Chr. zugeschrieben wird. Ausgehend von 2 werden die Vielfachen jeder gefundenen Primzahl mechanisch durchgestrichen; was übrig bleibt, ist prim. Da nur einfache, wiederholte Operationen nötig sind, eignet es sich gut für die Computerimplementierung.

Da die gesamte Berechnung im Browser läuft, ist die Obergrenze auf 1.000.000 begrenzt. Darüber hinauszugehen würde den Rechenaufwand stark erhöhen und könnte den Browser zum Stocken bringen.

Der Primzahlsatz liefert eine geschätzte Obergrenze für die N-te Primzahl, und das Sieb wird über diesen Bereich ausgeführt, um sie exakt zu finden. Abfragen bis zur 1.000.000. Primzahl werden unterstützt.

Bei vielen Ergebnissen werden nur die ersten 1.000 angezeigt, der Rest wird nur als Anzahl zusammengefasst. Die schrittweise Visualisierung ist nur für Obergrenzen von 400 oder weniger verfügbar.
ツールくん

Ü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.

Alle Wissenstexte ansehen

Nutzer, die dieses Tool angesehen haben, sahen auch

Primzahl-Prüfer — Faktorzerlegung & Rechenschritte

Prüfe sofort, ob eine Zahl (bis 10.000.000) eine Primzahl ist. Zeigt die Probedivision, die Primfaktorzerlegung und die vorherige/nächste Primzahl. Kostenlos.

Primfaktorzerlegung Rechner (bis 1.000.000)

Zerlege eine beliebige ganze Zahl N (2 bis 1.000.000) sofort in Primfaktoren. Zeigt Schritt-für-Schritt-Division, Teiler, Teileranzahl und Teilersumme. Mit Referenztabelle 1–100.

ggT- & kgV-Rechner

Geben Sie zwei positive ganze Zahlen ein, um mit dem euklidischen Algorithmus den größten gemeinsamen Teiler (ggT) zu finden – mit Anzeige jedes einzelnen Rechenschritts. Das kleinste gemeinsame Vielfache (kgV) wird glei...

Modulare-Arithmetik-Rechner (Mod-Rechner)

Ein Rechner für modulare Arithmetik mit 4 Modi: Grundlegendes Mod, modulare Addition/Subtraktion/Multiplikation, modulare Potenzierung (schnelle Potenzierung durch wiederholtes Quadrieren) und modulares Inverses (erweite...

Chinesischer-Restsatz-Rechner (CRT) — Simultane Kongruenzen lösen

Löst ein System simultaner Kongruenzen x ≡ a₁ (mod n₁), x ≡ a₂ (mod n₂)... mit dem chinesischen Restsatz. Prüft automatisch, ob die Moduln paarweise teilerfremd sind, und liefert die kleinste nicht-negative Lösung sowie...

Eulersche Phi-Funktion (φ) Rechner

Gib eine ganze Zahl N (1 bis 1.000.000) ein, um sofort die Anzahl der zu N teilerfremden ganzen Zahlen von 1 bis N (Eulersche φ-Funktion φ(N)) zu berechnen, inklusive Primfaktorzerlegung und verwendeter Formel. Mit einer...