# Primzahlen berechnen



## Consti (2. November 2004)

Ich lerne PHP und habe mir jetzt (leider) mehr oder weniger in den Kopf gesetzt, ein Script zu schreiben, welches Zahlen zwischen einem Bereich x bis y prüft, ob sie Primzahlen sind.
Ich bin daher erst mal mit der Hauptprozedur angefangen (ist eine feste Zahl x eine Primzahl).
Hier mein Ergebnis:


```
//Variblen festlegen
$testzahl = 79;		//Zahl, die getestet werden soll, ob sie ein Primzahl ist
$teiler = 2;		         //Durch diese Zahl wird geteilt
$primzahl = false;

do
	{
	if ($testzahl/2 >= $teiler)
		{
		if ($testzahl%$teiler = 0)
			{
			$primzahl = true;
			echo "Die Zahl ".$testzahl." ist keine Primzahl";
			}
		else
			{
			$teiler++;
			};
		}
	else
		{
		echo "Die Zahl ist ".$testzahl." eine Primzahl!<br>";
		};
	}
while ($primzahl=false);
```

Leider ist alles ein wenig verrutscht, aber ich möchte noch eben ein paar Worte sagen.
Zu Anfang wird erstmal eine Zahl festgelegt, die geprüft werden soll (bei mir 79 - ist eine Primzahl).
Nun geht die Do-Schleife los: es soll nur weitergehen, wenn die Hälfte der $testzahl grösser als der $teiler ist (weil: Wenn Testzahl=79 wäre, und der $teiler 40 ist, kann es keinen Wert (von 1 verschieden) mehr geben, der "ganz" ist.
So, das ist in diesem Fall gegeben, da 79/2=39,5 Grösser als 2 (=$teiler) ist.
Wenn nun die $testzahl ohne Rest durch den $teiler teilbar ist, dann ist die Zahl keine Primzahl.
Die bool-Variable wird auf true gesetzt (somit ist unten die while-Bedingung ungültig) und es sollte echo "Die Zahl ist keine Primzahl" ausgegben werden.
Falls die Zahl nur MIT Rest teilber ist, wird der $teiler um 1 erhöht und die Schleife beginnt nachher wieder mit der Prüfung ob die Hälfte des $testzahl usw...

Falls nun der $teiler grösser als die Hälfte des $testzahl ist, wird der Else-Teil ausgeführt, und die Zahl ist eine Primzahl!

Aber das Script läuft bei mir nicht. Es zeigt KEINES der beiden Echos an - und ich weiss nicht, wo der Fehler liegt.
Hab error_reporting(E_ALL) stehen und der meckert aber auch nicht rum!

Irgendwo ist ein Logikfehler, doch leider find ich ihn nicht! Wäre nett, wenn ihr mir helfen könntet!

Meines Wissens nach, GIBT es eine Funktion isPrime(); aber die möchte ich eigentlich nicht nutzen, da es ja auch anders gehen MUSS!

Danke schon mal für die Hilfe!


----------



## EM-Autotechnik (2. November 2004)

hi,

versuchs mal hiermit... (nicht getestet)


```
$deineZahl = 75;    //testzahl (nicht ohne Rest durch 2 teilbar)

function primzal($zahl)
{ 
    $check = $zahl/2;    //teile durch 2

    if(strstr($check, "."))    //prüfe ob Nachkommastelle
        return false;
    else
        return true;
} 

if(primzahl($deineZahl))
    echo "$deineZahl ist eine Primzahl";
else
    echo "$deineZahl ist keine Primzahl";
```

beste Grüße!


----------



## Consti (2. November 2004)

Also, wenn man die so kopiert bekommt man einen Fatal Error (ist aber leicht zu beheben, da du bei der funktion primza[[H]]l das H vergessen hast. Das konnte man aber recht schnell lösen, aber 79 erkennt das Script NICHT als Primzahl, obwohl es eine ist *g*.
Ich versteh dein Script zwar nicht so ganz, aber wo wird denn entschieden, ob die Zahl 79 nicht vllt durch 3 oder 4 oder sonstwas teilbar ist.


----------



## EM-Autotechnik (2. November 2004)

Hi,
ja hast recht 


```
$deineZahl = 75;    //testzahl (nicht ohne Rest durch 2 teilbar) 

function primzahl($zahl) 
{ 
    $teileDurch = array(  //Dein Array mit den Zahlen, durch die geteilt werden soll
        '2',
        '3',
        '4',    //usw.....
    );

    foreach($teileDurch AS $div)
    {
        $check = $zahl/$div;    //teile durch $div 

        if(strstr($check, "."))    //prüfe ob Nachkommastelle 
            return false; 
    }
    
    return true; 
} 

if(primzahl($deineZahl)) 
    echo "$deineZahl ist eine Primzahl"; 
else 
    echo "$deineZahl ist keine Primzahl";
```

oder


```
$deineZahl = 75;    //testzahl (nicht ohne Rest durch 2 teilbar) 

function primzahl($zahl) 
{ 
    $pruefeBis = 100;   //bis zu welche "ganzen" Zahl soll geprüft werden

    for($i = 1; $i<=$pruefeBis; $i++)
    {
        $check = $zahl/$i;    //teile durch $i 

        if(strstr($check, "."))    //prüfe ob Nachkommastelle 
            return false; 
    }
    
    return true; 
} 

if(primzahl($deineZahl)) 
    echo "$deineZahl ist eine Primzahl"; 
else 
    echo "$deineZahl ist keine Primzahl";
```

Hoffe das klappt alles...  wieder nicht getestet


----------



## fh_study (2. November 2004)

Mehrere Fehler gefunden. Zunächst hast du ne Klasse Endlosschleife gebaut indem du while($primzahl=false) geschrieben hast. Wenn schon heißt das $primzahl==false, sonst wird einfach false jedesmal neu in $primzahl geschrieben, und das geht natürlich bis in alle Ewigkeit. Außerdem bewirkt while(!$primzahl) das gleiche glaube ich.
Des weiteren fehlt dir eine Abbruchbedingung wenn es keine Primzahl ist. In deiner Schleife wird nur abgebrochen, wenn es eine Primzahl ist indem du $primzahl auf true setzt, aber wenn es keine Primzahl ist, dann bleibt es immer false. Dies kannst du einfach umgehen, indem du hinter
echo "Die Zahl ist ".$testzahl." eine Primzahl!<br>";
einfach
break;
schreibst. Das break Kommando beendet die while Schleife. 
Ein paar syntaktische Fehler hast du auch noch drin, z.B. gehört hinter eine geschweifte Klammer niemals ein Semikolon!

else 
            { 
            $teiler++; 
            }; <------ ganz böse

Ach so sehe gerade bei dir :

if ($testzahl%$teiler = 0) das heißt natürlich auch if( ($testzahl / $teiler) == 0 )

mit nur einem = setzt du immer Werte nur == ist ein Vergleich genauso wie <= >= usw. nur < und > machen da eine Ausnahme

Ansonsten sollte es funktionieren


----------



## vogtländer (3. November 2004)

Mal ein paar Takte zum Thema Algorithmierung:

PHP also Programmieren lernen ist zwar gut und schön aber vergiss das Algorithmieren nicht, denn bei deinem Problem - nämlich Primzahlen aus einem Bereich von Zahlen ermitteln - wird dann zu einem sehr langwierigen Problem, wenn deine Zahlen und besonders deine Zahlenbereiche sehr groß werden. Deshalb solltest du bei solchen Problemen genau überlegen, wie du den Algorithmus optimieren kannst.

Dazu gab es hier schonmal einen Thread (schau mal unten bei den verwandten Themen), an dieser Stelle will ich aber mal ein paar wesentliche Dinge sagen:

1. Die Schleife muss nicht bis zur Hälfte der zu prüfenden Zahl laufen sondern nur bis zur Wurzel.
2. Sowohl Zähler als auch Nenner werden immer gleich um 2 erhöht, wobei die Zahlen natürlich ungerade sind. 
3. Mitunter ist es sinnvoll, die Primzahlen bis - sagen wir z.B. - 997 zu speichern und zunächst nur mit diesen Zahlen zu testen und erst wenn dann Wurzel(Testzahl) noch nicht erreicht ist bei 1001 weiterzutesten.


----------



## Kerwin (3. November 2004)

Hab neulich auch mal sowas gebastelt geschrieben

```
<?php
function primtest($n)
{
    for ($teiler=2;$teiler*$teiler<=$n;$teiler++)
    {
        $z = $n % $teiler;
        if ($z == 0) // keine Primzahl
        {
            return false;
        }
    }
    // keinen Teiler gefunden, also Primzahl
    return true;
}
	
for($x=2;$x<=1000;$x++)
{
    if (primtest($x))
        echo "<font color = red><b>$x </b></font>";
    else
        echo "<font color = blue>$x </font>";
}
?>
```


----------



## alkaline (3. November 2004)

Ich möchte auch noch meinen Senf zu diesem Thema dazugeben.
Also um wirklich ernsthaft Primzahlen zu testen, würde ich auf einen probabilistischen Primzahlen-Test zurückgreifen. Eine Möglichkeit dazu ist der sogenannte Miller Rabin Primzahlentest. Ein relativ simpler Algorithmus, der dir, je nach Anzahl von Durchläufen, zu einer gewissen Wahrscheinlichkeit sagt, ob die Zahl prim ist. Google spuckt ne Menge zu dem Test aus...


----------



## Consti (3. November 2004)

Also erst mal Danke, dass einer die ganzen Fehler daraus gefunden hat!

Eigentlich sind es ja alle "dumme" Fehler, die ich eigentlich auch hätte selber finden können / müssen. Naja, gut, ich habe das Script jetzt soweit fertig.

Es ist sicherlich richtig, dass das Script nicht unbedingt für den Server die günstigste Variante ist, Primzahlen zu berechnen - aber darum geht es mir eigentlich auch nicht. Ich will das Script am Ende ja auch gar nicht benutzen - es war mehr so als kleine Übung gedacht, und wenn ich die Primzahlen zwischen 1 und 1000 berechne, dauert es schon ein wenig, bis mein kleiner Server (P2,233) das Ergebnis am Ende ausspuckt. Was passiert, wenn er das ganze zwischen 1 und 10000 machen soll, dann geht er wohl noch mehr in die Knie!

Aber zum "wirklichen" Berechnen, ist das Script bestimmt nicht geeignet - es war nur mal ein kleiner Versuch.
Hier jetzt meine fertige Lösung - für die dies noch interessiert (Man kann die eingaben zzt nur im Code selber vornehmen, da ich von Formulairen noch keine Ahnung habe (evtl. könnte man das ja noch mit $_GET('start') und $_GET('stop") machen - aber mal sehn!

Vielen Dank für die schnelle Hilfe!


```
<?php

error_reporting(E_ALL);
//Überschrift / Titel
echo "<h2>Dieses Script testet, ob ein Zahl \$testzahl eine Primzahl ist</h2><br>";
echo "Primzahlen<br>";

//Variblen festlegen
$start = 1;				//Mit dieser Zahl wird begonnen
$stop = 1000;			//MIt dieser Zahl wird das Script beendet
$testzahl = $start;		//Zahl, die getestet werden soll, ob sie ein Primzahl ist
$teiler = 2;			//Durch diese Zahl wird geteilt
$ergebnis = false;		
$anzahl_primzahlen = 0;	//Dieser Zähler zählt alle gefundenen Primzahlen

if ($start <= $stop)
	{
	while ($testzahl <= $stop)
		{
		do
			{
			if ($teiler <= ($testzahl/2))
				{
				if (($testzahl%$teiler) == 0)
					{
					//echo "Die Zahl ".$testzahl." ist keine Primzahl<br>";
					$ergebnis = true;
					}
				else
					{
					$teiler++;
					}
				}
			else
				{
				echo $testzahl.",	";
				//echo "Die Zahl ist ".$testzahl." eine Primzahl!<br>";
				$ergebnis = true;
				$anzahl_primzahlen++;
				}
			}
			while ($ergebnis == false);
		
		$teiler = 2;			//$teiler auf Ursprung zurücksetzen
		$testzahl++;			//nächste Zahl testen
		$ergebnis = false;
		}
	 }
else
	{
	echo "Die Zahl \$start ist grösser als die Zahl \$stop! Bitte Eingaben korrigieren!";
	}
echo "<h2>Statisktik</h2>";				//eine kleine Statistik
echo "\$start = ".$start."<br>";
echo "\$stop = ".$stop."<br>";
echo "Es wurden ".$anzahl_primzahlen." Primzahlen im Bereich von ".$start." bis ".$stop." gefunden!<br><br>";
?>
```


----------

