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>