Auf dieser Seite können Sie sich die Primfaktorzerlegung ganzer Zahlen darstellen lassen:
Beschreibung
Bereits im Kapitel über Javascript habe ich ein Programm zur Berechnung der Primfaktoren vorgestellt. Da Javascript aber (fast) keine Möglichkeit bietet, auf Dateien zuzugreifen, müssen die Primzahlen, die als Faktoren in Frage kommen, jedes Mal neu berechnet werden.
Da ich gerade php lerne, war die Primfaktorzerlegung ein gutes kleines Beispiel, um den Umgang mit Dateien zu üben. Die Idee: Die mit o.g. Javascript-Program berechneten Primzahlen in einer Datei hinterlegen und diese auslesen, um die Zerlegung zu berechnen.
Um auch anspruchsvollere Zerlegungsaufgaben lösen zu können, soll die Datei möglichst viele Primzahlen enthalten. Deshalb können zur Laufzeit des Programms nicht alle Primzahlen gleichzeitig in den Arbeitsspeicher (eine Feldvariable) geladen werden. Andererseits sollen sie nicht alle einzeln geladen werden, weil Festplattenzugriffe langsam sind.
Als Kompromiss wurde das zeilenweise Einlesen gewählt: Die Datei prim.csv (ACHTUNG: 21MB) enthält die Primzahlen von 2 bis 40.000.003 und zwar jeweils 25 in einer Zeile. Dieser Wert wurde völlig willkürlich gewählt, müsste aber natürlich auf die Größe des Arbeitsspeichers angepasst werden.
Sollten für eine Zerlegungsaufgabe Primzahlen erforderlich sein, die größer sind als 40.000.003, erscheint in der Teilerliste ein entsprechender Hinweis, dass weitere Faktoren existieren. Man könnte an dieser Stelle die Berechnung der weiteren Primzahlen anstoßen, da die Laufzeit von php-Skripts aber serverseitig begrenzt ist, erschien das nicht sinnvoll.
Listing
Nachfolgend sehen Sie das php-Listing, mit dem diese Primfaktorzerlegung berechnet wurde:
$farbe = array('#ffff99','#aaccff'); //Hintergrundfarben für Tabellenzeilen
$toggle = 1; //Variable zum Wechseln der Hintergrundfarbe
$primzahldatei = 'prim.csv'; //Datei in der Primzahlen durch Komma getrennt hinterlegt sind
//Die Primzahlen müssen sortiert sein, kleine zuerst
//Die Datei wird zeilenweise gelesen, auch am Ende der Zeilen steht ein Komma
$primzahlen = fopen($primzahldatei, r);
$von = (int) $_POST[min];
$bis = (int) $_POST[max];
for ($i = $von; $i <= $bis; $i++) { //Schleife über alle Zahlen, für die die Zerlegung berechnet werden soll
$toggle++;
$toggle %= 2; //Wechsel der Hintergrundfarbe
echo "<tr><td align='right' bgcolor=$farbe[$toggle]>$i =</td><td bgcolor=$farbe[$toggle]>"; //Tabellenüberschrift
rewind($primzahlen); //Bei jeder neuen Zahl muss wieder am Beginn der Primzahldatei zu lesen begonnen werden
$prim = fgetcsv($primzahlen); //Eine Zeile Primzahlen einlesen
$index = 0; //Zeiger auf die gerade benutzte Primzahl im Array $prim
$teiler = (int) $prim[$index];
$flag = false; //Anziger, ob für diese Zahl ein Teiler gefunden wurde
$zahl = $i; //Es kann nicht die Schleifenvariable selbst benutzt werden, weil $zahl im Algorithmus verändert wird.
while(1 != $zahl) { //$zahl wird so lange durch passende Teiler dividiert, bis das Ergebnis 1 ist
if (0 == $zahl % $teiler) { //Teiler gefunden
$zahl /= $teiler;
if ($zahl > 1) echo "$teiler * "; // Multiplikationszeichen * nicht beim letzten Teiler anhängen
else {
if (!$flag) echo 'Primzahl!';
//Wenn der gefundene Teiler gleichzeitig erster und letzter ist, ist $zahl eine Primzahl
else echo $teiler; //Ausgabe des letzten Teilers
}
$flag = true; //es gibt Teiler
} //end if Teiler gefunden
else {
$index ++; //nächste Primzahl probieren,
if ($index >= count($prim)-1) { //Primzahlen nachladen, minus 1 wegen Komma am Ende der Primzahlzeilen
if (feof($primzahlen)) { //Nachladen nicht mehr möglich, keine mehr da!
echo 'Primzahldatei am Ende! Weitere Zerlegung nicht möglich';
$zahl = 1; //Abbrechen der Zerlegung
} //end if eof
else {
$prim = fgetcsv($primzahlen); //Nächste Primzahlzeile lesen
$index = 0; //mit der ersten neuen Primzahl beginnen
} // end else eof
} //end if
} //end else (kein Teiler)
$teiler = $prim[$index]; //nächsten Teiler lesen
} //end while
echo "</td></tr>\n"; //Zeilenende der Ausgabetabelle
} //end for $i
fclose($primzahlen); //Datei schließen
echo '</table>';//Ende der Ausgabetabelle
Falls diese Seite ohne Navigationsleiste angezeigt wird, aktivieren Sie Javascript oder klicken Sie hier!