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: 5.1975250244141E-5 sec
Suche Primzahlen im Intervall 1 bis

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:
12345
678910

2.)
Jetzt fangen wir an mit der ersten Schleife und da die Eingabe nicht 1 sein kann, also bei zwei...
<? 
 
for( <= 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(
<= 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:
12345
678910

4 ist damit keine Primzahl!!!

Die innere Schleife läuft noch weiter, $mult ist jetzt 3:
<?
          
             
while(<= 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:
12345
678910

6 ist auch keine Primzahl!!!
.
.
.

4.)
Einen haben wir noch... $mult jetzt 5:
<?

             
while(<= 10) {        //5 * 2 = 10 Also ist die Schleife noch gültig
                 
$p[10] = false// 10 also auch false
                 
$mult++;  //jetzt 5+1
             
}
        
?>

Tabelle danach:
12345
678910

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(<= 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:
12345
678910


6.)
Innere Schleife läuft wieder weiter....
<?

          
             
while(<= 10) {        //3 * 3 = 9 Also ist die Schleife gültig
                 
$p[9] = false// 9 ist false
                 
$mult++;
             }
     
?>

Tabelle:
12345
678910

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:
12345
678910

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