Sieb Des Eratosthenes in PHP

Was man in der Schule gerade so mit Java lösen konnte habe ich in PHP nochmal ein bisschen schöner realisiert. Warum muss man überhaupt zwei Sprachen können? Ich wäre dafür, dass jeder mit der Sprache programmiert die er gut kann :-P. Typisch Lehrplan.

Es ging diesmal um das „Sieb Des Eratosthenes“.
Eine Methode um Primzahlen ausfindig machen zu können. Das Sieb besteht aus einem Raster, wie folgt:

1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100

Auf dieses Raster wird das „Sieb“ angewendet, bei jedem „Siebvorgang“ wird eine Schicht an „Nicht-Primzahlen“ abgeschöpft, bzw. es fallen nur die Primzahlen durch. Dazu wird die erste Reihe der Tabelle genommen (Hier die Zahlen 2-10), eigentlich sind es die Zahlen 2 – √100!

Die erste Reihe wird durchgegangen, angefangen bei der 2 werden alle Vielfachen der 2 weggestrichen, also alle geraden Zahlen fallen weg. Weiter geht es mit der 3 (Die ist noch nicht weggestrichen!) nun fallen alle Vielfachen der 3 weg. Nach diesen beiden Vorgängen sieht die Tabelle wie folgt aus:

1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100

Nun kommt man an einen, in der Programmierung, kniffeligen Punkt. Die 4 wurde bereits als Vielfaches der 2 weggestrichen, das Programm muss die 4 überspringen und weitergehen bis eine Zahl zwischen 2 und √100 noch nicht weggestrichen ist. Als nächstes findet das Sieb die 5 und streicht alle Vielfachen der 5 weg. Die 6 ist bereits als Vielfaches von der 2 gestrichen (Würde auch als Vielfaches von 3 „nochmal“ gestrichen werden!). Die 7 ist in diesem Beispiel die letzte Zahl dessen Vielfache gestrichen werden. Nach diesen beiden Programmschritten sieht die Tabelle wie folgt aus:

1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100

Für dieses Modell wären jetzt alle Zahlen der ersten Reihe belegt, bzw. nicht mehr ungetestet. Dadurch kann man nun sagen, dass alle anderen Zahlen (ohne Hintergrundfarbe) Primzahlen sind. Da wir das Ganze im Unterricht mit dem Programm „BlueJ“ geschrieben haben, dachte ich mir (Da ich PHP sowieso besser kann :-P), dass ich das Sieb in PHP schreibe. Grafisch nicht gerade ansprechend, aber funktionsfähig habe ich ein kleines Programm dazu rausgebracht.

-> Zum Programm

Wer das Script haben möchte kann sich gerne bei mir melden.