Kurzantwort: Das Sieb des Eratosthenes findet alle Primzahlen bis zu einer Grenze, indem man die Vielfachen jeder Primzahl streicht. Übrig bleiben die Primzahlen.
Was ist das Sieb des Eratosthenes?
Das Sieb des Eratosthenes ist ein einfaches Verfahren, um alle Primzahlen bis zu einer Grenze zu finden. Man streicht systematisch alle Vielfachen jeder Primzahl – übrig bleiben die Primzahlen.
Schritt für Schritt
- Schreibe alle Zahlen von 2 bis zur Grenze auf.
- Die erste nicht gestrichene Zahl (2) ist prim. Streiche alle Vielfachen von 2.
- Nimm die nächste nicht gestrichene Zahl (3). Streiche alle Vielfachen von 3.
- Wiederhole mit 5, 7, … bis zur Wurzel der Grenze.
- Alle nicht gestrichenen Zahlen sind Primzahlen.
Beispiel bis 100
Die markierten Zahlen sind die 25 Primzahlen, die das Sieb bis 100 übrig lässt:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100
Selbst erzeugen
Der Primzahl-Rechner nutzt genau dieses Sieb, um Listen bis zu einer Grenze zu erzeugen.
Häufige Fragen
Wie funktioniert das Sieb des Eratosthenes?
Man streicht der Reihe nach alle Vielfachen jeder Primzahl; die nicht gestrichenen Zahlen sind prim.
Bis wohin muss man streichen?
Bis zur Quadratwurzel der Grenze – danach sind alle übrigen Zahlen automatisch prim.
Wer war Eratosthenes?
Ein griechischer Gelehrter der Antike, nach dem das Verfahren benannt ist.
Wie viele Primzahlen gibt es bis 100?
Genau 25.