Sieb des Eratosthenes
Zur "Berechnung" von allen Primen in einem bestimmten Zahlenbereich, bedient man sich einer Technik, die Eratosthenes von Mykene entdedckt hat. Diese nennt sich Sieb des Eratosthenes. Das Prinzip des Siebes beruht darauf, dass Primzahlen niemals komposite Zahlen sein können. Aus dem Zahlenbreich werden einfach alle kompositen Zahlen gestrichen, der Rest sind Primen.
Zuerst wird der Zahlenbereich initialisiert.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Dann werden 0 und 1 aus dem Bereich gestrichen (sind eh nicht prim und der Zeiger wird auf das erste freie n gesetzt (in diesem Falle 2)
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Nun werden alle Vielfachen von 2 aus dem Bereich gestrichen
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Nun wird der Zeiger auf die nächste freie Zahl gesetzt (3). Da kleinere Vielfache als das Quadrat von 3 (also 6) bereits durch die Vielfachen von 2 abgedeckt sind, kann man direkt mit n² beginnen. Ausserdem sind alle Zahlen die vor n² kommen nun Primen.
2 3 5 7 9 11 13 15 17 19
Die verbleibenden Zahlen sind nun alles Primzahlen, denn die nächste zu prüfende Zahl wäre ja 5. Da die Berechnung jeweils mit dem Quadrat der Zahl beginnt läge das kleinste Vielfache ausserhalb des Zahelenbereichs. Die Abbruchbedingung für die Prüfung ist so festgelegt:
Sobald n >= √m ist, kann man abbrechen.
Im Folgenden also alle Primzahlen zwischen 0 und 20
2 3 5 7 11 13 17 19