Primzahl berechnen

Stef · 6. August 2016

Hey zusammen,

ich habe auf ner webseite eine aufgabe gefunden, wo man die Primzahlen berechnen muss.

Hier der originale code der seite, dazu habe ich mal paar fragen:

PHP

<?php
/* Aufgabe : Primzahlen




Mit den bisherigen Informationen, können wir auch ein erstes kleines Programm schreiben.




Ich möchte ein Programm haben, welches mir alle Primzahlen zwischen 1 und 100 ausgibt. Für jene die Primzahlen nicht kennen: 




Eine Primzahl ist nur durch 1 und sich selbst teilbar. Zum Beispiel die 7.




Wichtig ist, dass Du probierst, selbst eine Lösung zu finden.




Hinweise:




   Schleifen
   Modulus
*/




for($i = 1; $i <= 100; $i++)
   {
   	$unteilbar = true;
	for($k = 2; $k < $i; $k++)
   		{
   			if(!($i % $k))
   			{
   				$unteilbar = false;
   				break;
   			}
   		}




   	if($unteilbar){
   	echo "Primzahl ist: " .$i . "<br>";
   }
}
?>

Alles anzeigen

1. Was ist den ein Modulus ?
2. Warum wird jetzt in die erste for schleife : $unteilbar = true reingeschrieben ?
Diese schleife erstellt doch nur die zahl 1 bis 100. Und man teilt dort auch nichts.
3. Die 2te for schleife wird ja gemacht zum teilen von $i und $k ?
4.

PHP

if(!($i % $k))
   			{
   				$unteilbar = false;
   				break;
   			}

Dieser code sagt ja. Wenn $i % $k nicht teilbar sind ist $unteilbar false. Was ist das % ? Warum wird da jetzt break verwendet?

Freue mich auf eure Hilfe.

Gruß, Stef

Basi · 6. August 2016

Modulus ist die Rechenoperation mit dem %-Zeichen. Dabei handelt es sich um eine Division, wobei der Rest ermittelt wird:

PHP

$division = 7 / 3; // 2.3333333333333
$modulus = 7 % 3; // 1 ( Die 3 passt 2 mal in die 7 [2 * 3 = 6] und als Rest bleibt 1)

$unteilbar ist jetzt der Indikator dafür, ob nach dem Durchlauf der zweiten Schleife eine Ausgabe stattfindet. Es wird jede Zahl bis zur aktuellen auf Teilbarkeit geprüft und wenn eine Teilbarkeit festgestellt wurde, wird $unteilbar auf false gesetzt und mittels break die innere Schleife abgebrochen. Da $unteilbar jetzt false ist, findet keine Ausgabe statt und es wird mit der nächsten Zahl weitergemacht.

Wenn eine teilbare Zahl gefunden wurde weiß man bereits, dass es sich um KEINE Primzahl handelt, die verbleibenden Zahlen zu prüfen ist daher nicht nötig. Deswegen kann man mittels break abbrechen.

Der Algorithmus eignet sich übrigens nicht für sehr große Zahlen, da die Anzahl der Durchläufe der Schleifen exponentiell wächst.

Du siehst schon warum ich sagte, dass Algorithmik vor Allem mit Mathematik zu tun hat

Die erste Schleife müsste übrigens auch bei 2 anfangen zu zählen. 1 ist keine Primzahl.

cottton · 6. August 2016

was Basi sagt und

1. Modulus http://php.net/manual/de/language.operators.arithmetic.php

Zitat

Rest von $a geteilt durch $b

Ich finde $unteilbar und $i $k sind schlecht gewählt.
Siehe Comments:

PHP

// !($a % $b)
// 
// 2 % 2 === 0
// ! "dreht das ergebnis um"
// also:
// !(0) egibt true
//
// var_dump(!(0)); // bool(true)
//
// in anderer schreibweise:
// $rest = $a % $b;
// if(!$rest) // wenn NICHT $rest 







// andere schreibweise:
for ($a = 1; $a <= 100; $a++) { // für alle zu prüfende zahlen 1 - 100
    $istPrimzahl = true;
    for ($b = 2; $b < $a; $b++) {  
        $rest = $a % $b; // zB 6 / 3 ergibt rest 0
        if ($rest === 0) { // zB 6 / 3 ergab 0, also nicht nur durch 1 und sich selbst teilbar
            $istPrimzahl = false;
            break; // unterbreche/beende die momentane schleife (2te for(...)),
            // denn wir haben festgestellt, dass es keine primzahl ist.
        }
    }
    if ($istPrimzahl) {
       echo "Primzahl ist: " . $a . "<br>";
    }
}

Alles anzeigen

Stef · 6. August 2016

Hey,

aso ok. So ist das.

Ja das sehe ich langsam. Am besten man schreibt erstmal was man alles braucht. Dann hat man schon sozusagen einen Plan. Ist besser finde ich. Da hat man eine struktur nach der man geht. Dann weiß man auch was zu machen ist und hat dann mehr ideen wie es machbar ist als wenn man nichts hinschreibt.

Danke für eure Hilfe.

Gruß,Stef

Primzahl berechnen

Jetzt mitmachen!

Teilen