Sieb des Eratosthenes: Quellcode
<HTML>
<HEAD>
<TITLE>Sieb des Eratosthenes</TITLE>
</HEAD>
<BODY TEXT="#000000" BGCOLOR="#F8F8FC">
<H1>Sieb des Eratosthenes</H1>
<?php
// PHP Version ab 5
// Bei groesserem $number das memory_limit erhoehen
// ini_set("memory_limit", "16384M");
$php_self = $_SERVER['PHP_SELF'];
// 664579 Primzahlen bis 10 000 000 in etwa 4 Sekunden berechnet !
// 5761455 Primzahlen bis 100 000 000 in etwa 75 Sekunden berechnet !
if (array_key_exists('number', $_POST)) $number = $_POST['number']; else $number = "0";
if (array_key_exists('spalten', $_POST)) $spalten = $_POST['spalten']; else $spalten = "100";
// Eingabe
echo "<FORM METHOD=POST NAME=eratosthenes ACTION=\"$php_self\">\n";
echo "<TABLE BORDER=0 CELLSPACING=4 CELLPADDING=4>\n";
echo "<TR>\n";
echo "<TD>Maximale Primzahl:</TD>\n";
echo "<TD><INPUT TYPE=TEXT NAME=number VALUE=\"$number\" SIZE=8 MAXLENGTH=8></TD>\n";
echo "<TD>(Mindest-)Anzahl Spalten:</TD>\n";
echo "<TD><INPUT TYPE=TEXT NAME=spalten VALUE=\"$spalten\" SIZE=4 MAXLENGTH=4></TD>\n";
echo "<TD><INPUT TYPE=SUBMIT VALUE=\"Go !\"></TD>\n";
echo "</TR>\n";
echo "</TABLE>\n";
echo "</FORM>\n";
if ($number > 0) {
$number_halbe = floor(($number-1)/2);
$prim = array();
// Start mit 2 statt 1 als Primzahl
$prim[0] = 2;
// Erzeugen mit Weglassen aller geraden Zahlen
for ($k = 1; $k <= $number_halbe; $k++) {
$prim[] = 2*$k+1;
}
// Vielfache streichen nur bis maximal sqrt(number), hier wegen Weglassen aller geraden Zahlen
$max = floor((sqrt($number)-1)/2);
// Es ist sinnvoll, beim Streichen der Vielfachen mit dem Quadrat der Primzahl zu beginnen, da alle kleineren Vielfachen bereits markiert sind
for ($k = 1; $k <= $max; $k++) {
$x = $prim[$k];
if ($x == 0) continue;
$nx = ($x*$x - $x)/2;
for ($m = $k+$nx; $m <= $number_halbe; $m = $m+$x) {
$prim[$m] = 0;
}
}
// Anzahl Primzahlen zaehlen
$gesamt = 0;
for ($k = 0; $k <= $number_halbe; $k++) {
if ($prim[$k] > 0) $gesamt++;
}
echo "$gesamt Primzahlen bis N = $number<BR>\n";
echo "<PRE>\n";
$ausgabe = "";
$anz = 0;
$gedruckt = 0;
for ($k = 0; $k <= $number_halbe; $k++) {
if ($prim[$k] > 0) {
// Alternative Ausgabeform:
// $ausgabe = $ausgabe . ", " . str_pad($prim[$k], 6, " ", STR_PAD_LEFT);
$ausgabe = $ausgabe . ", " . $prim[$k];
$anz++;
$gedruckt++;
}
// Alternative Ausgabeform:
// if ($anz == $spalten) {
if (strlen($ausgabe) >= $spalten) {
$ausgabe = substr($ausgabe, 2);
if ($gedruckt < $gesamt) echo "$ausgabe,\n";
else echo "$ausgabe\n";
$ausgabe = "";
$anz = 0;
}
}
if ($anz > 0) {
$ausgabe = substr($ausgabe, 2);
echo "$ausgabe\n";
}
echo "</PRE>\n";
}
?>
</BODY>
</HTML>