Über das Sieb des Eratosthenes - so funktioniert das Primzahlsieb

Eratosthenes von Kyrene

Eratosthenes lebte etwa von 276 bis 194 v. Chr. und leitete die große Bibliothek von Alexandria. Bekannt ist er vor allem dafür, dass er die Größe der Erde aus der Länge der Schatten in zwei Städten bestimmte. Das Sieb ist nach ihm benannt, weil Nikomachos von Gerasa es in seiner Einführung in die Arithmetik, geschrieben um 100 n. Chr., als seine Methode beschrieb.

So funktioniert das Sieb

Schreiben Sie die Zahlen von 2 bis N auf. Die erste Zahl, 2, ist eine Primzahl: Streichen Sie 4, 6, 8 und jedes weitere Vielfache von 2. Die nächste Zahl, die übrig ist, 3, ist eine Primzahl: Streichen Sie 9, 12, 15 und so weiter. Machen Sie mit 5, 7 und den nächsten übrigen Zahlen weiter. Eine Zahl, die nie gestrichen wird, hat keinen kleineren Teiler, also ist sie eine Primzahl.

Bei der Wurzel aufhören

Jede zusammengesetzte Zahl bis N hat einen Primfaktor, der nicht größer als die Wurzel aus N ist. Sobald p² größer als N ist, gibt es also nichts mehr zu streichen. Für die Primzahlen bis 100 brauchen Sie nur 2, 3, 5 und 7, für 1000 die Primzahlen bis 31.

Wie schnell ist es?

Das Sieb braucht etwa N log log N Schritte, das wächst nur wenig schneller als N selbst. Computer nutzen es noch heute, oft in Stücken als segmentiertes Sieb, um Primzahlen bis in die Milliarden aufzulisten. Um zu prüfen, ob eine einzelne große Zahl eine Primzahl ist, sind andere Verfahren schneller.

Häufig gestellte Fragen

Wer hat das Sieb des Eratosthenes erfunden?

Es ist nach Eratosthenes von Kyrene benannt, einem griechischen Gelehrten des dritten Jahrhunderts v. Chr. Die älteste schriftliche Beschreibung stammt von Nikomachos von Gerasa, um 100 n. Chr.

Warum beginnt das Sieb bei p² mit dem Streichen?

Jedes kleinere Vielfache von p hat einen kleineren Primfaktor, also hat eine kleinere Primzahl es schon gestrichen.

Wie viele Primzahlen gibt es unter 1000?

Es gibt 168 Primzahlen unter 1000. Die größte ist 997.