Sieb des Eratosthenes: Quellcode

<HTML>
<HEAD>
<TITLE>Sieb des Eratosthenes</TITLE>
</HEAD>

<BODY TEXT="#000000" BGCOLOR="#F8F8FC">

<H1>Sieb des Eratosthenes</H1>

<?

// 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($ausgabe2);
            if (
$gedruckt $gesamt) echo "$ausgabe,\n";
            else echo 
"$ausgabe\n";
            
$ausgabe "";
            
$anz 0;
        }
    }
    if (
$anz 0) {
        
$ausgabe substr($ausgabe2);
        echo 
"$ausgabe\n";
    }
    
    echo 
"</PRE>\n";
}

?>

</BODY>
</HTML>