Das nach Eratosthenes von Kyrene (ca. 275 v. Chr. – ca. 194 v. Chr.) als Sieb des Eratosthenes benannte Verfahren dient der Bestimmung der Primzahlen bis zu einer beliebigen Grenze. Das Verfahren war schon lange vor Eratosthenes bekannt. Der vielseitige Gelehrte prägte jedoch den Begriff Sieb.
Wie funktioniert das Sieb des Eratosthenes?
Das Verfahren funktioniert so, dass man aus dem betrachteten Zahlenbereich alle Zahlen streicht, die keine Primzahlen sein können.
Übrig bleiben die Primzahlen im Zahlenbereich.
Dabei nutzt man die Bedingung für Primzahlen aus, dass eine Primzahl nur durch 1 und durch sich selbst teilbar ist. Eine Primzahl ist somit kein Vielfaches einer anderen Zahl, denn sonst wäre diese andere Zahl ja auch ein Teiler.
Anleitung für das Sieb des Eratosthenes
Schreiben Sie also alle Zahlen im betrachteten Zahlenbereich auf. Eins ist nicht prim und kann gestrichen werden.
Nun nehmen Sie jeweils die nächste noch nicht gestrichene Zahl – sie ist eine Primzahl, weil sie kein Vielfaches einer anderen ist.
Streichen Sie alle ihre Vielfachen, da diese nicht prim sein können.
Dies wiederholen Sie so lange, bis der Zahlenbereich erschöpft ist.
Optimierung des Sieb des Eratosthenes?
Zwei Beobachtungen beschleunigen das Verfahren deutlich:
- Mit den Streichungen der Vielfachen kann bei der Quadratzahl begonnen werden, da alle kleineren Vielfachen bereits durch vorhergehende Primzahlen abgedeckt sind.
- Die Streichungen selbst müssen nur bei Zahlen durchgeführt werden, die kleiner oder gleich der Wurzel der Zahl sind, die den Zahlenbereich begrenzt, da Primfaktoren einer zusammengesetzten Zahl immer kleiner oder gleich ihrer Wurzel sind.
Beispiel zum Sieb des Eratosthenes
Als beispielhafte Anwendung des Sieb des Eratosthenes bestimmen Sie mit ihm die Primzahlen bis 100.
