[Milka_Kuh]

Hallo, ich habe eine Frage:
Ich muss in php etwas erstellen, wo ich eine Zahl eingeben kann und das zeigt mir an, ob die eingegebene Zahl eine Primzahl ist oder nicht.
Zurzeit hab ich das:
<?php
$a = $_POST["Zahl"];
$count = 2;

if ($a = 1){
echo "Die Zahl " $a " ist keine Primzahl!";
}else{
while ($count <= 1000){
if ($a % $count = 0) {
echo "Die Zahl " $a " ist eine Primzahl!";
}else{
$count +1;
}
}
}
if (mod != 0){
echo "Die Zahl " $a " ist keine Primzahl!";
?>

ich habe jedoch keine Ahnung ob das stimmt...kann mir vielleicht irgendwer bei meinem Problem helfen? Danke!

[Mr. Floppy]

Willkommen im Forum!

Mit PHP kann ich Dir nicht weiterhelfen, aber zumindest beim Algorithmus könntest Du Dir das mal angucken. Du überprüfst z.B. nur, ob der Rest einer Division 0 ist. Das reicht als Bedingung aber nicht aus (4 % 2 = 0, aber 4 ist nicht prim). Andersrum wird ein Schuh draus. Wenn sich bis zur zu prüfenden Zahl keine Divisionen mit einem Rest von 0 finden, handelt es sich um eine Primzahl. Aus Effizienzgründen sollte man davon ausgehen, daß es sich um eine Primzahl handelt und abbrechen, wenn man doch einen Teiler findet.

Dieser Beitrag wurde von Mr. Floppy bearbeitet: 16. Mai 2012 - 19:29

[Witi]

Schau dir mal den Sieb des Eratosthenes an. Das ist mWn der einfachste Algorithmus um sich Primzahlen ausgeben zu lassen.

Wenn du dich traust, kannst du es auch mit etwas komplizierterem versuchen, wie dem Miller Rabin Test oder AKS.

[deezee]

maximal bis zur hälfte von $a zählen und nur auf ungrade Ziffern prüfen

Dieser Beitrag wurde von deezee bearbeitet: 16. Mai 2012 - 21:28

[__42__]

$a % $count = 0
Tests auf Gleichheit werden in PHP mit "==" bzw. "===" durchgeführt.

[Ludacris]

<?php
$i = (int)$_GET["zahl"];
for($i=1; $i<=10000; $i++){
	if($i==1){
		echo $i."<br>";
	}
	else if($i==2 || $i==3){
		echo $i."<br>";
	}
	else if(($i%2)!=0){
		if(($i%3)!=0){
			echo $i."<br>";
		}
	}

}
?>

der Code gibt dir Primzahlen bis 10000 aus

<?php
$i = (int)$_GET["zahl"];
if($i==2 || $i==3){
	echo $i." ist eine Primzahl.<br>";
}
else if(($i%2)!=0){
	if(($i%3)!=0){
		echo $i." ist eine Primzahl.<br>";
	}
	else 
	{
		echo $i." ist keine Primzahl.<br>";
	}
}
else 
{
	echo $i." ist keine Primzahl.<br>";
}
?>

und der hier gibt dir aus ob die zahl im URL Parameter eine Primzahl ist oder nicht

[TO_Webmaster]

 Zitat (Ludacris: 17. Mai 2012 - 21:34)

der Code gibt dir Primzahlen bis 10000 aus

Hmm, der gibt z.B. auch 25 (=5*5) aus.

Hier meine Implementierung:

<?PHP

function modpot( $p, $c, $m )
{
	$r = 1;
	
	while( $c ){
		if( $c % 2 )
			$r = ( $r * $p ) % $m;
		$p = ( $p * $p ) % $m;
		$c = $c >> 1;
	}
	
	return $r;
}

function isprime( $n ){

	if( $n < 3 )
		return $n - 1;

	if( $n % 2 == 0 )
		return 0;
	
	$d = $n - 1;
	$s = 1;
	
	while( ( $d = $d >> 1 ) % 2 == 0 )
		++$s;
		
	$z = array( 2, 7, 61 );
		
	foreach( $z as $a ){
	
		if( $a < $n && modpot( $a, $d, $n ) != 1 ){
			$c = 1;
			for( $r = 0; $r < $s; ++$r )
				if( modpot( $a, ( 1 << $r ) * $d, $n ) == $n - 1 )
					$c = 0;
			if( $c )
				return 0;
		}
	}
	
	return 1;
}




$zahl = (int) $_GET['n'];

if( $zahl <= 0 || (string) $zahl !== (string) $_GET['n'] ){
	echo 'grr!';
} else {
	echo $zahl . ' ist ' . ( isprime( $zahl ) ? 'wahrscheinlich' : 'nicht' ) . ' prim.<br />';
}

echo '<br /><br />Beispielprimzahlabfragen:<br /><br />';

for( $i = 0; ++$i < 10000; ){
	echo $i . ' ist ' . ( isprime( $i ) ? 'wahrscheinlich' : 'nicht' ) . ' prim.<br />';
}

?>

MfG TO_Webmaster

[Ludacris]

stimmt, ich hab die überprüfung auf 5er und 7er nicht eingebaut. mit

for($i=1; $i<=10000; $i++){
	if($i==1){
		echo $i."<br>";
	}
	else if($i==2 || $i==3){
		echo $i."<br>";
	}
	else if(($i%2)!=0){
		if(($i%3)!=0){
			if(($i%5) !=0){
				if(($i%7)!=7){
					echo $i."<br>";
				}
			}
		}
	}
}

sollte es gehen

[__42__]

 Zitat (Ludacris: 18. Mai 2012 - 00:09)

stimmt, ich hab die überprüfung auf 5er und 7er nicht eingebaut. mit

for($i=1; $i<=10000; $i++){
	if($i==1){
		echo $i."<br>";
	}
	else if($i==2 || $i==3){
		echo $i."<br>";
	}
	else if(($i%2)!=0){
		if(($i%3)!=0){
			if(($i%5) !=0){
				if(($i%7)!=7){
					echo $i."<br>";
				}
			}
		}
	}
}

sollte es gehen

11*11=121

[Mr. Floppy]

@Ludacris
Ganz so einfach ist es dann doch nicht. TO_Webmaster und __42__ haben ja schon darauf hingewiesen, wo das Problem liegt. Deine Methode findet nur Primzahlen, die kleiner als das Quadrat der nächst größeren Primzahl sind. Beispiel: Wenn Du die 11 jetzt auch noch hinzufügst, gibt's den nächsten Fehler bei 13². Der Code müßte also alle Primzahlen für die Moduloberechnung bereits enthalten. Dann würde aber auch eine simple Liste genügen. Die ist aber dummerweise unendlich groß.

Dieser Beitrag wurde von Mr. Floppy bearbeitet: 18. Mai 2012 - 09:09

[Leshrac]

 Zitat (Witi: 16. Mai 2012 - 19:32)

Schau dir mal den Sieb des Eratosthenes an. Das ist mWn der einfachste Algorithmus um sich Primzahlen ausgeben zu lassen.

Yup.

Zitat

Wenn du dich traust, kannst du es auch mit etwas komplizierterem versuchen, wie dem Miller Rabin Test oder AKS.

Da gibt es eine "fertigloesung" vom MIT, mal so als inspiration

Ansonsten, je groesser die werte werden desto groesser wird auch der rechenaufwand mit solch einem einfachen script. Man kann das natuerlich noch ein bisschen optimieren, indem man alle zahlen ueber 5 ausschliesst die nicht auf 1, 3, 7 oder 9 enden. Sieht dann so aus:

function isPrime($n)
{
if ($n > 5)
{
if (! in_array(substr($n, -1), array(1, 3, 7, 9))) // quick win
return false;

for ($i=2; $i<=floor(sqrt($n)); $i )
{
if ($n % $i === 0)
return false;
}
}
elseif ($n == 4) // 2, 3 and 5 are prime
return false;

return true;
}

Dieser Beitrag wurde von Leshrac bearbeitet: 18. Mai 2012 - 17:02