Im Intervall 1 bis 100 gefundene Primzahlen:
1 -
2 -
3 -
5 -
7 -
11 -
13 -
17 -
19 -
23 -
29 -
31 -
37 -
41 -
43 -
47 -
53 -
59 -
61 -
67 -
71 -
73 -
79 -
83 -
89 -
97 -
26 Primzahlen gefunden!
Dauer: 0.00034213066101074 sec
Zugegeben, die Berechnung von Primzahlen bedarf mehr als 3-4 zeilen PHP code.
Ich habe hier eine Methode angewand die sich "Sieb des Erastothenes" nennt, Wikipedia war mir da eine Hilfe :)
Bitte keine Bereiche größer 100.000 eingeben...
Zum Code:
Die Funktion "prim($N)" gibt alle Primzahlen von 1 bis zum mitgelieferten Wert als Array aus....
Aufruf mit prim(Bereich)
<?PHP
function prim($N) {
if($N < 2) return false; // Eingabe muss größer oder gleich 2 sein
for($i = 1; $i <= $N; $i++) $p[$i] = true; // initialisiere das Array mit jedem Eintrag TRUE
for($i = 2; $i <= ceil(sqrt($N)); $i++) { // durchlaufe das Array, ceil rundet das Ergebnis der Wurzel auf. Wir prüfen nur bis zum Quadrat des Bereichs, das reicht...
if($p[$i]) { // falls der Eintrag noch TRUE ist nehme ich eine Primzahl an
$mult = 2;<br>
while($mult * $i <= $N) { //Zuerst nehmen wir i mal 2, dann i mal 3 usw. bis i mal n kleiner ist als der Zahlenbereich den wir prüfen
$p[$mult * $i] = false; // dann setzen wir das vielfache als FALSE denn das ist keine Primzahl...
$mult++;
}
}
}
return $p; // Ausgabe als Array. Die Primzahlen sind TRUE sind und der Rest FALSE. z.B. $p[4] = False od. $p[7] = TRUE<br>
}
?>
Schritt für Schritt
Wer das ganze verstehen möchte sollte hier weiterlesen, der Rest nimmts bitte als gottgegeben...
1.)
Nehmen wir uns einen Bereich von 1 bis 10 und schreiben uns die verfügbaren Zahlen auf wie im Programm geschehen bei dieser Zeile:
<?
for($i = 1; $i <= $N; $i++) $p[$i] = true; // initialisiere das Array mit jedem Eintrag TRUE
?>
In einer Tabelle sieht das ungefähr so aus:
2.)
Jetzt fangen wir an mit der ersten Schleife und da die Eingabe nicht 1 sein kann, also bei zwei...
<?
for( 2 <= ceil(sqrt(10)); $i++) { // Wurzel aus 10 = 3,1622... aufgerundet also 4. Zwei ist kleiner als 4 also wird die Schleife ausgeführt...
if($p[2]) { // Ist TRUE da wir ja am anfang alle Zahlen bis 10 TRUE gesetzt haben... also Bedingung erfüllt - weiter
$mult = 2;
while(2 * 2 <= 10) { //2 * 2 = 4 also kleiner 10 also Wahr --> schleifenbedingung erfüllt
$p[4] = false; // hier setzen wir also das ergebnis aus 2*2 = 4 also den inhalt des arrays[4] auf false
$mult++; //entspricht in diesem durchlauf also 2+1
}
}
}?>
Das Ergebnis in unserer Tabelle nach dem ersten durchlauf:
4 ist damit keine Primzahl!!!
Die innere Schleife läuft noch weiter, $mult ist jetzt 3:
<?
while(3 * 2 <= 10) { //3 * 2 = 6 also kleiner 10 also Wahr --> schleifenbedingung erfüllt
$p[6] = false; // hier setzen wir also das ergebnis aus 3*2 = 6 also den inhalt des arrays[6] auf false
$mult++; //entspricht in diesem durchlauf dann 3+1
}
?>
Tabelle:
6 ist auch keine Primzahl!!!
.
.
.
4.)
Einen haben wir noch... $mult jetzt 5:
<?
while(5 * 2 <= 10) { //5 * 2 = 10 Also ist die Schleife noch gültig
$p[10] = false; // 10 also auch false
$mult++; //jetzt 5+1
}
?>
Tabelle danach:
10 ist keine Primzahl
Beim nächsten Durchgang währe $mult*2 grösser als 10 also endet die Schleife hier...
5.)
Jetzt inkrementiert $i in der Hauptschleife und ist damit 3...
3 ist immernoch kleiner als 4, die Schleife läuft also durch:
<?
if($p[3]) { // 3 ist in unserer Tabelle noch nicht als FALSE markiert worden also immernoch WAHR, es geht weiter...
while(2 * 3 <= 10) { //2 * 3 = 6 Also ist die Schleife gültig
$p[6] = false; // 6 ist false
$mult++;
}
?>
An der Tabelle ändert sich nichts da 6 schon vorher als nicht-Primzahl markiert wurde:
6.)
Innere Schleife läuft wieder weiter....
<?
while(3 * 3 <= 10) { //3 * 3 = 9 Also ist die Schleife gültig
$p[9] = false; // 9 ist false
$mult++;
}
?>
Tabelle:
Als nächstes währe $mult = 4 also 4 * 3 = 12. Damit grösser 10 also endet die innere Schleife hier wieder...
7.)
Hier wirds interessant: $i wird jetzt 4 und damit ist die Bedingung if($p[4]) nicht erfüllt, da wir ja bereits 4 als Primzahl ausgeschlossen haben...
Die innere Schleife läuft also nicht durch und $i wird damit jetzt schon durch $i++ zu 5...
Da 5 jedoch grösser ist als die (aufgerundete) Wurzel aus 10 ist die Laufbedingung der Hauptschleife auch nicht mehr erfüllt und die Funktion endet hier
mit Return $p.
Und $p[] enthält die Tabelle die wir bisher erstellt haben:
Damit sind alle Primzahlen zwischen 1 und 10 bestimmt... Sie lauten:
1 -2 - 3 - 5 - 7
FERTIG!!!
Ich hoffe dieses wirre Gequassel versteht jemand ;) dennoch...
Wikipedia rules!!!
Author der Seite: Florian Vetter (florianvetter@gmx.de) - letzte Änderung 14.01.2008