 |
Eratosthenes (ca.300v.Chr.), griechischer Mathematiker,
erdachte ein Verfahren, um systematisch alle Primzahlen bis zu einer
vorgegebenen Grenze zu erzeugen. Anstatt
jede einzelne natürliche Zahl
einem aufwendigen Test mittels Divisionen zu unterziehen, wandte Erathostenes
ein raffinierteres Verfahren an, das bezeichnenderweise auch als Sieb des
Erathostenes in die Geschichte der Mathematik einging..
Ausgangssituation: Benötigt wird eine Liste der ersten natürlichen
Zahlen, beginnend mit 2. Die Länge der Liste gibt die Obergrenze vor, bis
zu der Primzahlen ermittelt werden. Die zusammengesetzen Zahlen (Produkte von
zwei kleineren Zahlen) in dieser Liste werden systematisch gestrichen. Die dann
übrigbleibenden ungestrichenen Zahlen sind die Primzahlen.
Dabei geht man folgendermaßen vor: Man nehme die erste, nicht-ausgestrichene
Zahl p der Liste. Diese Zahl p ist prim. Man streiche alle Vielfachen von p in
dieser Liste. (Dabei braucht man erst beim p-fachen, also bei der Zahl
p2 zu beginnen, da alle kleineren Vielfachen kp, k<p, bereits
ausgestrichen wurden.)
Dieses Verfahren wird
so oft angewendet, bis die gesamte Liste abgearbeitet ist. Das Schöne an
diesem Verfahren ist: Man braucht keine Multiplikationen. Es genügt
völlig, von jedem gestrichenen Wert kp um p Schritte weiterzugehen,
um den nächsten Kandidaten
für das Streichen aus der Liste zu erhalten.
Der besondere Gewinn des Verfahrens liegt vor allem in folgendem: Erreicht
man die erste Primzahl, deren Quadrat nicht mehr in der Liste vorkommt, so ist
das Verfahren beendet und alle noch ungestrichenen Zahlen der Liste sind jetzt
definitiv Primzahlen. Im Beispiel links bedeutet dies, dass bei Erreichen der
Primzahl 11 das Verfahren abgeschlossen ist. Man brauchte also nur die
Vielfachen der vier Primzahlen 2,3,5,7 zu streichen, um alle 30 Primzahlen
unterhalb von 120 zu finden.
|