primzahl

[NineBall]

hiho, ich komme bei einer aufgabe nicht weiter. ich soll herausfinden ob 7358193 eine primzahl ist oder nicht. wenn ich es aufrufe kommt immer "keine Primzahl, obwohl ich auch mal es durch 7 ersetzt habe. also:
for ($i=2;$i<=6;$i++) {
} if (7%($i)==0) {
dann kommt auch immer keine primzahl.


<?php
for ($i=2;$i<=7358192;$i++) {
} if (7358193%($i)==0) {
echo "keine Primzahl\n";
} else {
echo "ist eine\n";

}
?>

[Gaert]

Hallo,

du solltest dir mal die geschweiften Klammern anschauen... der For Block ist leer!

So wärs richtig:



<?php
for ($i=2;$i<=7358192;$i++) {
if (7358193%($i)==0) {
echo "keine Primzahl\n";
} else {
echo "ist eine\n";
}

}
?>

[NineBall]

so wie du es gemacht hast ist auch nicht richtig, weil er dann 7,3 mio mal ausgibt "ist eine"

[undefined]

Was du da machst nennt man Resourcen Fresser :D


<?php
set_time_limit(10);
$Zahl = (int)7358192;
for ( $i = 2 ; $i <= $Zahl; $i++ ) {
if ( ( $Zahl % $i ) == 0 )
echo $i . "<br/>";
}
?>

[mehlvogel]

<?php
$notprim = false;
for ($i=2;$i<=7358192 && !$notprim;$i++) {
$notprim = $notprim && 7358193%($i)==0;
}
if ($notprim) echo "Keine ";
echo "Primzahl";
?>

[Gaert]

so wie du es gemacht hast ist auch nicht richtig, weil er dann 7,3 mio mal ausgibt "ist eine"
Ich wollte eigentlich nur zeigen dass die Schachtelung falsch ist :D

[msi]

machs so:




$zahl = 7358193;

$not_a_prim = 0;
for ($i=2; $i<$zahl; $i+=2) {
if ( $zahl % $i == 0 ) {
$not_a_prim = 1;
break;
}
if ( $i == 2 ) $i=1;
}

if ( $not_a_prim ) {
echo "ist keine Primzahl";
} else {
echo "ist eine Primzahl";
}



lässt sich natürlich noch optimieren, dazu kannst ja mal im internet suchen.

an die anderen:
wenn bewiesen ist, dass es keine primzahl ist, sollte man natürlich um zeit zu sparen auch aus der for-schleife rauspringen.
Desweiteren kann man sich die durch 2 teilbaren zahlen (außer 2 selbst) gleich sparen und beim for gleich um 2 erhöhen, so dass man also
2,3,5,7,9,11,13,usw überprüft.

[mehlvogel]

Man könnte auch das Sieb des Erastosthenes machen ;) Aber um es auf die Spitze zu treiben hätte ich hier nen Interessanten Artikel für die geneigte Leserschaft: Fun with prime Numbers (http://www.troubleshooters.com/codecorn/primenumbers/primenumbers.htm)

[NineBall]

Was du da machst nennt man Resourcen Fresser


<?php
set_time_limit(10);
$Zahl = (int)7358192;
for ( $i = 2 ; $i <= $Zahl; $i++ ) {
if ( ( $Zahl % $i ) == 0 )
echo $i . "<br/>";
}
?>

dann kommt sowas heraus
3
9
181
543
1629
4517
13551
40653
817577
2452731
7358193
und ich weiß nicht was es heißen soll, weil 3 ist eine primzahl und dann kommt 9, obwohl es keine primzahl ist.



<?php
$notprim = false;
for ($i=2;$i<=7358192 && !$notprim;$i++) {
$notprim = $notprim && 7358193%($i)==0;
}
if ($notprim) echo "Keine ";
echo "Primzahl";
?>

eigentlich ist es keine primzahl, wie ich mittlerweile im internet mit rechnern herausgefunden habe, aber bei diesen script ist alles eine primzahl, egal wie ich die werte verändere.
z.b. so

<?php
$notprim = false;
for ($i=2;$i<=5 && !$notprim;$i++) {
$notprim = $notprim &&6%($i)==0;
}
if ($notprim) echo "Keine ";
echo "Primzahl";
?>
@msi: dein scipt funktioniert wunderbar, nur ich verstehe es "noch" nicht.
:confused: bin noch nicht so weit, aber danke an euch alle.

[msi]

Hallo,

mehlvogel hat in seinem script geschribene:
$notprim = $notprim && 7358193%($i)==0;
das ist falsch, es müsste $notprim = $notprim || 7358193%($i)==0; heißen. dann sollte seins auch gehen (auch wenns langsamer als meins ist ;) )

undefined hat scheinbar gar nicht verstandne, was du willst.

ich jetzt erklär ich dir noch mein script:

$zahl = 7358193; // zahl festlegen, die analysiert wird

$not_a_prim = 0; // not_a_prim wird auf 1 gesetzt, falls bewiesen ist, dass es keine Primzahl ist.

// die untersuchung beginnt bei 2 und geht bis $zahl/2 (aufgerundet) weil größere zahlen als zerlegungne nicht mehr in frage kommen, weil die kleinen nötigen zerleger (auch primzahlen) schon weg sind.
du kannst natürlich auch einfach $i<$zahl schreiben, dann braucht das script nur etwas länger.
wir erhöhen $i bei jedem durchlauf um 2, um die zahlen, die durch 2 teilbar sind und somit eh keine primzahlen sind und keine teiler mehr darstellen gleich auszuschlißen und ein bisschen zeit zu sparen.

for ($i=2; $i<ceil($zahl/2; $i+=2) {
// falls $zahl geteilt durch $i keienn rest ergibt, ist es keine primzahl
wir setzen also $not_a_prim auf 1 und beenden die forschleife mit break
if ( $zahl % $i == 0 ) {
$not_a_prim = 1;
break;
}

// da wir uns ein bisschen arbeit ersparen und das ganze nur mit zahlen die nicht durch 2 teilbar sind testen müssen wir jetzt $i zurücksetzen. bevor das $i+=2 von der for schleife $i erhöht.
if ( $i == 2 ) $i=1;
}

// der for code wird also mit folgenden $i's durchgeführt: 2 3 5 7 9 11 13 ...
nach dem ersten 2 wäre 4 dran und genau deshalb setzen wir es um eins zurück auf 2, damit es dann 3 wird.

if ( $not_a_prim ) {
echo "ist keine Primzahl";
} else {
echo "ist eine Primzahl";
}

@mehlvogel:
ich würde mir an deiner stelle so einen code abgewöhnen, da er im nachhinein recht schwer zu verstehen ist und man entspr. lang braucht um fehler zu finden.

> Man könnte auch das Sieb des Erastosthenes machen
Mit dem Sieb des Eratosthenes kriegst du alle Primzahlen bis zu einer best. Zahl raus. Wenn du so überprüfst ob die große dabei ist, glaube ich, braucht man wesentlich mehr rechenzeit, als wenn man das einfach so überprüft.

[NineBall]

nochmals danke, du hast mir die erleuchtung gebracht. :D *schleimschleim*
kannst du mir sagen wieso mein script nicht funktioniert?
es zeigt jetzt auch bei jeder zahl keine Primzahl an.

[undefined]

Hallo,
undefined hat scheinbar gar nicht verstandne, was du willst.

Jup da hast du Recht ich habe erst jetzt gesehen was gefragt ist :rolleyes:
Asche über mein Haupt :D


<?php
set_time_limit(10);
$Zahl = (int)7358193;
$pr = true;
for ( $i = 2; $i <= (int)sqrt( $Zahl ); $i+=2 )
$pr = ( bcmod( $Zahl, $i ) == 0 ) ? false : true;

if ( $pr )
echo "Primzahl";

?>

[msi]

Jup da hast du Recht ich habe erst jetzt gesehen was gefragt ist :rolleyes:
Asche über mein Haupt :D


<?php
set_time_limit(10);
$Zahl = (int)7358193;
$pr = true;
for ( $i = 2; $i <= (int)sqrt( $Zahl ); $i+=2 )
$pr = ( bcmod( $Zahl, $i ) == 0 ) ? false : true;

if ( $pr )
echo "Primzahl";

?>


hehe, aber auch so wird jede nicht durch 2 teilbare zahl eine primzahl sein, du durchläufst ja nur 2,4,6,.... richitg wäre 2,5,7,9,...
außerdem solltest du in der bedingung der forschleife noch das $pr einbauen also for ($i=2;$i<=(int)sqrt($Zahl) && $pr; $i+=2).
aber das limit bei sqrt($zahl) zu setzen ist natürlich sinnvoller, als meins.



<?php
for ($i=2;$i<=7358192;$i++) {
} if (7358193%($i)==0) {
echo "keine Primzahl\n";
} else {
echo "ist eine\n";

}
?>

wieso das nicht geht?
du durchläufst die for schleife ohne code, dh reines durchzählen ohne sinn
und dannach (nachdem $i mit 2 bis 7368192 durchgelaufen ist) überprrüfst du ob es durch den letzden wert, den $i angenommen hat (7368192) teilbar ist. und das ist es nicht.

die perfekte variante lautet:


$zahl = 7358193;

$not_a_prim = 0;

for ($i=2; $i<sqrt($zahl); $i+=2) {
if ( $zahl % $i == 0 ) {
$not_a_prim = 1;
break;
}

if ( $i==2 ) $i=1;
}

if ( $not_a_prim ) {
echo "ist keine Primzahl";
} else {
echo "ist eine Primzahl";
}