Eratosthenes (276-194 v. Chr.), Bibliothekar der großen Bibliothek von Alexandria, hat ein Siebverfahren angegeben, mit dem man alle Primzahlen bis zu einer bestimmten Zahl berechnet, die man vorgeben kann. Gauss schreibt: "Ich habe sehr oft einzelne unbeschäftige Viertelstunden verwandt, um bald hie bald dort eine Chilliade (Bem.: 1000er-Intervall) abzuzählen."(Glatfeld, 1993).
D. N. Lehmer hat 1909 ein Buch mit der Faktorisierung der ersten 10 Millionen Zahlen und 1914 ein Heft mit den Primzahlen kleiner als 10 Millionen herausgegeben. Diese Tabellen wurden mit dem Sieb des Eratosthenes berechnet, das nachher besprochen wird.
Ein J. P. Kulik (1773-1863), ein Österreicher, hat 20 Jahre seines Lebens damit verbracht, von Hand eine Tabelle der Primzahlen bis 100 Millionen zu erstellen. Der Band von 12.642.600 bis 22.852.800 ist verlorengegangen (Conway, 1997). Heute würden sich die Herren in den Allerwertesten beißen, wenn sie wüßten, daß ein Computer diese Arbeit in wenigen Minuten leistet.
Wie funktioniert nun das Sieb des Eratosthenes?
| Man schreibt alle Zahlen hin, bis zur höchsten Zahl, bis zu der man die Primzahlen berechnen will. | 1 2 3 4 5 6 7 8 9 10 11 12 13 |
| Die 1 ist per Definition keine Primzahl, sie wird deshalb gestrichen. | |
| Nun nimmt man die erste ungestrichene Zahl, also die 2 und streicht alle Vielfachen der 2, aber nicht die 2 selbst. | |
| So verfährt man nun mit der nächsten ungestrichenen Zahl, also der 3. | |
| Die größte Zahl, deren Vielfache man streichen muß, ist maximal so groß die Wurzel der Zahl, bis zu der man die Reihe aufgestellt hat. In diesem Fall ist man nun fertig, da 5 schon größer ist als die Wurzel von 13. Alle ungestrichenen Zahlen sind nun Primzahlen. |
Auf der folgenden Seite habe ich ein Sieb des Erathosthenes für die Zahlen bis maximal 999 (abhängig von der Anzahl pro Zeile) in Javascript programmiert. Es funktioniert allerdings nur mit dem Internet Explorer von Microsoft, nicht mit dem Netscape ab Version 4.x. Für Netscape 4.x (nicht höher) habe ich eine eigene Version.
Weitere Informationen z.B. unter http://www.math.utah.edu/~alfeld/Eratosthenes.html oder
über die Linkliste.
zurück 