Primzahlenberechnung

[DX-Rated]

Hallo,

ich möchte mir die Primzahlen bis 1000 mittels PHP im Browser ausgeben lassen. Ich hab ein Script gebastelt, das aber nicht so recht funzt. Ich schätze es ist ein Denkfehler, keine Ahnung. Bin in PHP noch Anfänger.

<?php


    $x = "";

    $y = "";

    $y <= $x;


    for ($x=1; $x<=1000; $x++) {

        for ($y=1; $y<=1000; $y++) {

            if ($x % $y > 0) {

                echo "$x ist eine Primzahl.<br>";

            }

        }

    }

?>[/PHP]

Ich muss ja jedes X zwischen 1 und 1000 durch jedes Y zwischen 1 und 1000 teilen, wobei Y niemals größer X sein darf.

Ich weiß nicht genau, wie bei diesem Script gerechnet wird, aber ich bekomme bei der Ausgabe die Zeile "1 ist eine Primzahl" ziemlich oft, schätzungsweise 300-400 mal, dann geht's bei "2 ist eine Primzahl" weiter, und das auch sehr oft. An der Stelle hab ich abgebrochen.

Ich möchte keine vollständige Lösung, vielleicht nur ein Tipp, was am abgebildeten Script falsch ist und evtl ein Denksanstoss in die richtige Richtung. Ich will das ja weitestgehen alleine schaffen. :-)

(Boardsuche hab ich genutzt, hat 3 Threads ausgespuckt, die mir aber nicht weitergeholfen haben

[Klotzkopp]

Dein Script entscheidet, dass eine Zahl eine Primzahl ist, wenn du eine Zahl gefunden hast, durch die die Zahl nicht teilbar ist.

Beispiel:

27 ist nicht durch 5 teilbar -> 27 ist eine Primzahl.

Das ist natürlich Quatsch.

Es reicht nicht, wenn du einen Nicht-Teiler findest. Du darfst keinen Teiler finden. Das kannst du aber erst entscheiden, wenn die innere Schleife durchgelaufen ist.

[Nobse]

Hallo,

echo("1. Primzahl: 2<br>\n");

  $anz = 1;

  for ($p = 3; $p < 1000; $p++) {

    for ($i = 2; $i < $p; $i++)

      if ($p % $i == 0)

        break;

    if ($i < $p)

      continue;

    $anz++;

    echo($anz.". Primzahl: ".$p."<br>\n");

  }[/PHP]

[kills]

google hilft!!

<p>

Primzahlen bis 1000:

</p>

<p>

<?php

  // 2 ausgeben

  echo("2");

  for ($p = 3; $p < 1000; $p++) {

    for ($i = 2; $i < $p; $i++)

      if ($p % $i == 0) // i ist Teiler: keine Primzahl 

        break;          // Test abbrechen

    if ($i == $p) // Schleife wurde komplett durchlaufen

      echo(" ".$p);

  }

?>

</p>





[/PHP]

[DX-Rated]

Danke schon mal. 'Ne Komplettlösung wollte ich aber eigentlich nicht

Hab's versucht, folgendermaßen zu lösen:

<?php


    $x = "";  // zu prüfende Zahl

    $y = "";  // Teiler


    for ($x = 3; $x <= 1000; $x++) {

        for ($y = 2; $y <= 1000; $y++) {

            // abbrechen, wenn ein Teiler gefunden wurde

            if ($x % $y == 0) {

                break;

            }

            // wenn kein Teiler gefunden wurde, Zahl als Primzahl ausgeben

            else {

                echo "$x ist eine Primzahl.<br>\n";

            }

        }

    }

?>[/PHP]

Was ist daran falsch? Die Ausgabe sieht ungefähr so aus:

3 ist eine Primzahl.

5 ist eine Primzahl.

5 ist eine Primzahl.

5 ist eine Primzahl.

7 ist eine Primzahl.

7 ist eine Primzahl.

7 ist eine Primzahl.

7 ist eine Primzahl.

7 ist eine Primzahl.

9 ist eine Primzahl.

11 ist eine Primzahl.

11 ist eine Primzahl.

11 ist eine Primzahl.

Oder bin ich einfach nur zu blöd dazu?

[Rohde]

Du gibst bei jedem Durchlauf der inneren Schleife gleich aus, daß $x eine Primzahl ist, bis ein ganzzahliger Teiler gefunden wurde. Das darfst Du natürlich erst nach dem kompletten Durchlauf der inneren Schleife machen. Außerdem reicht es aus, wenn die innere Schleife nur bis zum Wert $x läuft, da darüber liegende $y-Werte sowieso keine ganzzahligen Teiler von $x sein werden. Um den Durchlauf noch ein wenig zu beschleunigen erhöhst Du den Wert für $x immer um zwei (weil teilbar durch zwei). Damit sparst Du Dir schon mal die Hälfte der Durchläufe. Du solltest übrigens nicht mit drei anfangen, sondern mit eins, da eins und zwei ebenfalls Primzahlen sind.