Programm 1: Primzahlen

Mit den bisherigen Informationen, können wir auch ein erstes kleines Programm schreiben.

Ich möchte ein Programm haben, welches mir alle Primzahlen zwischen 1 und 100 ausgibt. Für jene die Primzahlen nicht kennen: Eine Primzahl ist nur durch 1 und sich selbst teilbar. Zum Beispiel die 7.

Wichtig ist, dass Du probierst, selbst eine Lösung zu finden.

Hinweise:

  • Schleifen
  • Modulus

Lösung

Dies ist die einfachste, bzw. leistungsschwächste Variante die mir einfiel.

<?PHP

//  Programm  ermittelt  Primzahlen

//  Schleife  die  uns  die  Zahlen  von  1  -  100  liefert
for  ($i  1$i  <=  100$i++)  {

   
//  Bei  jeder  neuen  Zahl  gehen  wir  zunächst  davon  aus,
    //  dass  sie  unteilbar  ist.  Das  merken  wir  uns.
   
$unteilbar  true;

   
//  Eine  Zweite  Schleife  zählt  bis  zu  unserer
    //  aktuell  zu  prüfenden  Zahl  minus  1  ($i-1)
    //  Und  beginnt  mit  2,  da  alle  Zahlen  durch  1  teilbar  sind
   
for  ($d  2$d  $i$d++)  {

         
//  Wenn  unsere  aktuelle  Zahl  $i
          //  durch  eine  kleinere  Zahl  teilbar  ist,
          //  gibt  Modulus  (%)  eine  0  zurück.
         
if(!($i  $d))  {
               
//  Wir  vermerken  dies  in  $unteilbar
               
$unteilbar  false;
               
//  Die  Schleife  kann  beendet  werden,
                //  es  reicht,  wenn  ein  einziger  Divisor  gefunden  wurde.
               
break;
          }
    }

   
//  Ausgabe  nur,  wenn  $unteilbar  true  bleibt,
    //  denn  dann  ist  es  eine  Primzahl
   
if  ($unteilbar)  {
          echo 
'Primzahl:  '.$i.'<br/>';
    }
}

?>

Ohne Kommentare

Damit Du ein Gefühl bekommst, wie viel tatsächlich an Programmcode notwendig ist, hier ein Mal ohne Kommentare. ABER bitte IMMER Kommentare beim Programmieren schreiben, auch wenn es noch so sinnlos erscheint.

<?PHP
for  ($i  1$i  <=  100$i++)  {
   
$unteilbar  true;
    for  (
$d  2$d  $i$d++)  {
          if(!(
$i  $d))  {
               
$unteilbar  false;
                break;
          }
    }
    if  (
$unteilbar)  {
          echo 
'Primzahl:  '.$i.'<br/>';
    }
}
?>

Gedanken

Ich hatte eine while-Schleife genommen, und ohne Limit Primzahlen ausgeben lassen. Die einzige Grenze war die Laufzeit von PHP-Programmen vom Webserver. Diese ist nämlich standardmäßig auf zwei Minuten eingestellt.

So konnte ich nach und nach Verbesserungen ausprobieren, und schauen, ob in der gleichen Zeit mehr Primzahlen ermittelt werden. So beschäftigt man sich ein wenig mit Mathe und Programmierung. Hier ein paar Hinweise.

  • Müssen auch gerade Zahlen geprüft werden?
  • Ist das erhöhen um 2 schneller mit der Addition ($i += 2;) oder zwei mal Inkrement hintereinander ($i++; $i++;)?
  • Hat es Sinn mit geraden Zahlen zu prüfen ($d)?
  • Hat es Sinn mit allen Zahlen zu prüfen, oder nur mit Primfaktoren?
  • Was hat die Wurzel mit Primzahlen zu tun?
  • Lohnt es sich bestimmte Zahlen zwischenzuspeichern, um mit denen eine Prüfung zu machen?
  • Was ist "Siebtechnik"?

Ich hatte dann um die fünf Versionen, und jede hatte eine signifikante Leistungsteigerung im Vergleich zur Vorversion.