Primzahlen
lima-city → Forum → Programmiersprachen → PHP, MySQL & .htaccess
ausgabe
beitrag
break
erklrung
extension
funktion
gedacht
hlfte
nchste primzahl
primzahl
quadrat
quelltext
quersumme
restwert
schlaufe
schleifen
sieb
teiler
zeile
zurck
-
hallo
ich habe eine neue idee zu meinem problem, leider kann ich es nicht umsetzen.
Könnt ihr mir helfen: Ich möchte, dass PHP alle Teiler von jeder Zahl zwischen 1 und 100 bestimmen. Falls es einen Teiler hat, soll eine 1 in einem Array speichern (mit "array_push"). Falls dann der gewünschte Array nur 2 mal die 1 beinhaltet (man kann das mit "count" herausfinden) ist es dann eine Primzahl, und er soll es aufschreiben.
Ich habe das x-mal ausprobiert und nix hat geklappt.
Bitte helft mir.
-
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
-
Ich wurde angefragt, wie das Sieb funktioniert.
Hier gibts ne Erklärung:
http://de.wikipedia.org/wiki/Sieb_des_Eratosthenes
<?php $bis = 1000; //Soweit soll gesucht werden $possible = array(); //In einem Array werden dann alle möglichen Zahlen //gespeichert for ($i = 3; $i <= $bis; $i=$i+2) //Alle ungeraden Zahlen, also jede 2te von 3 $possible[$i] = true; //wird am anfang als Primzahl angesehen //Von 3 wird jetzt bis zur Quadratwurzel von $bis eine Zahl ausgesucht //Nach der Quadratwurzel kehren sich die Zahlenpaare um: 6x5 = 5x6 for ($i = 3; $i <= bcsqrt($bis, 3); $i=$i+2) if ($possible[$i]==true) //Wenn die Zahl eine Prim ist for ($j=$i*$i; $j <= $bis; $j=$j+$i) //werden alle Vielfachen von der $possible[$j]=false; //Zahl keine Prim sein /* bei der zweiten for-schlaufe muss ich erst beim Quadrat beginnen Alle kleineren Zahlen sind schon markiert, also: $j=$i*$i $i ist die Zahl, $j das Quadrat Dann wird zum Quadrat bei jedem schritte die Zahl addiert: $j += $i Beispiel ab 5: Fünf ist nicht markiert, also ist es eine Prim 25,30,.. 100 markieren, sind also keine Prim Hier sieht man, warum man erst beim Quadrat mit markieren beginnen muss: 20 wäre schon von 2 markiert worden, 15 von drei... 6 ist markiert, also keine Primzahl 7 ist nicht markiert, markiere 49 ... */ //Zum Schluss noch die Ausgabe echo "2 <br />"; //die 2 muss ich zusätzlich ausgeben for($i=3; $i <=$bis; $i=$i+2) //von 3 bis zum ende in 2er schritten if($possible[$i]==true) //wenn es eine prim ist echo $i . '<br />'; //diese ausgeben ?>
Beitrag geaendert: 4.4.2007 15:58:05 von nigolaz
Beitrag geaendert: 4.4.2007 19:16:49 von nigolaz -
deine erklärung hat mir sehr geholfen, danke.
eines würde ich dir raten: die Kommentare die du machst können nur eine Zeile lang dauern. Es gibt aber auch Kommentare die dürfen mehr als eine Zeile gehen, wenn du es so machst:
<?php echo "Hallo"; /* Hier wird Hallo geschrieben und zwar ganz langweilig und ohne irgendwelche besionderen sachen*/ ?>
ist nur als bemerkung gedacht ;)
vielleicht kennst du es ja und wendest es einfach nicht an...
Beitrag geaendert: 4.4.2007 17:26:42 von xasa -
xasa schrieb:
hat niemand eine Idee, wie ich meine Idee (siehe weiter oben) verwirklichen kann??
In dem Script das ich geposted habe ist rel. weit oben eine While() Schleife in der alle Teiler durchgegangen werden. Hilft dir das weiter? Sonst frage einfach noch einmal nach.
// Zu der Zeile
ergeb=zahl%div;
Der "%" Operator gibt den Rest einer Division zurück.
Damit solltest du weiter kommen sonst sage bitte genau wo es hängt.
Beitrag geaendert: 5.4.2007 22:38:15 von satan -
hat niemand eine Idee, wie ich meine Idee (siehe weiter oben) verwirklichen kann??
Allerdings treibt dieses Verfahren die Serverlast ziemlich nach oben. -
danke
das hat mir schon recht weit geholfen. -
hallo
ich habe eine neue idee zu meinem problem, leider kann ich es nicht umsetzen.
Könnt ihr mir helfen: Ich möchte, dass PHP alle Teiler von jeder Zahl zwischen 1 und 100 bestimmen. Falls es einen Teiler hat, soll eine 1 in einem Array speichern (mit "array_push"). Falls dann der gewünschte Array nur 2 mal die 1 beinhaltet (man kann das mit "count" herausfinden) ist es dann eine Primzahl, und er soll es aufschreiben.
Ich habe das x-mal ausprobiert und nix hat geklappt. Bitte helft mir.
Wofür brauchst du das eigentlich? Willst du einfach die Primzahlen suchen oder wirklich die Zahl zerlegen? -
nigolaz schrieb:
Wofür brauchst du das eigentlich? Willst du einfach die Primzahlen suchen oder wirklich die Zahl zerlegen?
ich will die primzahlen suchen, und zwar so einfach wie es geht. ich weiss, meine idee ist zwar nicht die einfachste, aber für mich die verständlichste. falls jemand eine noch einfachere methode hat, kann er sie mir bitte schicken? (PN oder einfach in diesem thread) -
(kleiner scherz am rande)
na primahlen sind die, die nur durch 1 und sich selbst teilbar sind...
ABER WARUM WILLST DU DAS DENN WISSEN? -
Also wenn du es wirklich einfach machen willst:
Du versuchst jede Zahl durch jede kleinere Zahl du teilen, wenns nie geht, ist's eine Prim.
Ist aber ziemlich langsam.
Könnte irgendwie so aussehen: (Habs nicht ausprobiert)
<?php //Welche Zahlen sollen durchsucht werden: $start = 2; $ende = 100; // Eine Schlaufe, die jede Zahl durchsucht: for($zahl = $start ; $zahl <= $ende ; $zahl ++) { $prim = true; //Ich nehme an, es ist eine Primzahl //Von 2 bis zur Zahl selbst... for($teiler = 2 ; $teiler < ($zahl/2) ; $teiler ++) { //ist i durch j teilbar? Wenn ja, ist der Restwert (%) = 0 if($zahl % $teiler == 0) { $prim = false; //die Zahl ist keine Prim break; //die 2te Schlaufe beenden } } if($prim) echo $zahl; } /* Die Erklärung: Zuerst habe ich eine grosse Schlaufe, die von $start bis $ende geht. Damit suche ich jede Zahl im gesuchten Bereich einzeln ab. Die aktuelle Zahl ist dann in $zahl gespeichert. Dann habe ich eine zweite Schleife, die von 2 bis zur Hälfte von $zahl geht. Nach der Hälfte von $zahl kehren sich die Werte um: 5x6 = 6x5... Diesen Wert speichere ich in $teiler. Jetzt prüfe ich, ob $zahl durch $teiler teilbar ist. Der Operator % gibt den Restwert zurück, wenn dieser 0 ist, ist die Zahl $zahl teilbar. Weil eine primzahl nicht durch andere Zahlen teilbar ist, setzes ich $prim auf false und beende die innere schleife mit break. Wenn die innere Schleife nie einen Teiler findet, ist $prim immer noch true und ich kann die Zahl als Primzahl ausgeben. */ ?>
Beitrag geaendert: 9.4.2007 10:12:34 von nigolaz -
nigolaz schrieb:
Also wenn du es wirklich einfach machen willst:
Du versuchst jede Zahl durch jede kleinere Zahl du teilen, wenns nie geht, ist's eine Prim.
Ist aber ziemlich langsam.
Könnte irgendwie so aussehen: (Habs nicht ausprobiert)
<?php //Welche Zahlen sollen durchsucht werden: $start = 2; $ende = 100; // Eine Schlaufe, die jede Zahl durchsucht: for($zahl = $start ; $zahl <= $ende ; $zahl ++) { $prim = true; //Ich nehme an, es ist eine Primzahl //Von 2 bis zur Zahl selbst... for($teiler = 2 ; $teiler < $zahl ; $teiler ++) { //ist i durch j teilbar? Wenn ja, ist der Restwert (%) = 0 if($zahl % $teiler == 0) { $prim = false; //die Zahl ist keine Prim break; //die 2te Schlaufe beenden } } if($prim) echo $zahl; } ?>
Beitrag geaendert: 7.4.2007 11:58:56 von nigolaz
danke, der code funktioniert. -
Du must nur bist zur hälfte der Zahl probieren dadurch wird der Code zu min etwas schneller sh. mein Code.
-
Stimmt. Aber die Frage war ein sehr simpler Code. Wenn es um die Geschwindigkeit geht:
1. Andere Sprache
2. Sie mal hier: http://nigolaz.lima-city.de/prim.php -
...da geb ich space-center recht!
Aber, hey' space-center ... was soll denn dieser Nutzername??? -
Ich wurde angefragt, wie mein zweiter Code funktioniert.
Ich habs jetzt oben hineingeschrieben. -
Ich hab mal, das meiner Meinung nach kürzeste Beispiel entbugt
und getestet...
So funktioniert´s nun:
<?php // init der Integer-Variable & String-Variable $i = 0; $s = ""; do{ // finde nächste Primzahl & liefere als String zurück $s = gmp_strval(gmp_nextprime($i)); // gebe String aus echo $s." "; // wandle Primzahl-String in Integer um $i = gmp_intval($s); } while($i<10000); // bis erste Primzahl über 10000 erreicht ist ?>
Grüßle & viel Spaß damit
Beitrag geaendert: 12.4.2007 13:44:40 von scout -
Leider ist diese Bibliothek GMP-Bibliothek, die gmp_nextprime zur Verfügung stellt auf Lima nicht verfügbar. Oder irre ich mich? Also bei mir läuft das Script nicht.
Ich werde die GMP-Bibliothek auf meinem Server packen. Mal sehn, wie schnell das ist... -
ja sorry hast Recht - lima-city hat die extension php_gmp.dll bzw. php_gmp.so nicht eingebunden. Aber evtl. kann man das ja irgendwie nachholen... werde ich morgen mal austesten.
Grüßle
Nachtrag:
ok theoretisch könnte man eine Extension so laden...
<?php // prüfe ob gmp-Extension geladen ist if (!extension_loaded('php_gmp')) { // lade gmp-Extension dynamisch (funzt nicht im Safe-Mode) if (!dl('php_gmp.dll')) { exit; } } ?>
...aber das ist an diverse Bedingungen geknüpft - unter anderem darf Safe-Mode nicht aktiviert sein.
Lima-City hat dies allerdings - verständlicher weise aktiviert - so dass die gmp-Funktionen nicht ausgeführt werden können.
Ich werde dies mal bei Wünschen mit angeben
Grüßle
Beitrag geaendert: 12.4.2007 13:54:34 von scout -
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
