Logik !?

[Severin]

Hallo,

Also, ich scheine irgendwie die Logik eines php Skriptes nicht so ganz zu verstehen. Ich muss gleich sagen, dieses Skript ist nur eine Spielerei (und Hausaufgabe....) ist,aber ich scheine die logik meines Skriptes trotzdem nicht so ganz nachvollziehen zu können.
Die Aufgabe ist, die Primzahlen von 0 bis 1000 ausgeben zu lassen.

Dieses Skript funktioniert wunderbar:
<?php
function chk_prime($number){
 $prime = true;
 for($i=2;$i<=sqrt($number);$i++){
  if($number % $i == 0){
  $prime = false;
  break;
  }
 }
 if($prime == false):
  return false;
 else:
  return true;
 endif;
}
$i = 0;
while($i < 1000){
 if(chk_prime($i)){
 echo $i."<br>";
 }
 $i++;
}
?>

wenn ich jezt allerdings das sqrt($number) weglasse, schreib es nur die zahlen 0 und 1.

und wenn ich anstatt sqrt($number) eine zahl (z.B. 900) schreibe,  schreibt das Skript 1 und die Primzahlen ab der definierten Zahl.

Warum? wo ist der Unterschied ob man die Quadratwurzel einer Zahl oder die Zahl selbst oder eine ganz normale Zahl nimmt?(Abgehsehen von der Höhe der Zahl, aber dann nur 0 und 1 zu schreiben ist doch auch irgendwie unlogisch).

gruß,
Severin

[Jan]

<< for($i=2;$i<=sqrt($number);$i++){

Das zweite Gleichzeichen ist der Übeltäter, korrekt muss es heißen:

for($i=2;$i<$number;$i++){

Sonst wird $number auch mit sich selbst verglichen und da muss er ja nun teilbar sein.

Viele Grüsse
Jan

[Sven Rautenberg]

Moin!

<< for($i=2;$i<=sqrt($number);$i++){

Das zweite Gleichzeichen ist der Übeltäter, korrekt muss es heißen:

for($i=2;$i<$number;$i++){

Sonst wird $number auch mit sich selbst verglichen und da muss er ja nun teilbar sein.

Die Sache mit der Quadratwurzel ist die: Eine Primzahl findet man aufwendig, aber sicher so, indem man alle kleineren Zahlen darauf prüft, ob die zu prüfende Zahl sich durch irgendeine kleinere Zahl teilen läßt. Wenn man also prüfen will, ob 1000 eine Primzahl ist, teilt man sie einfach durch alle Zahlen von 2 bis 999 und schaut, ob der Rest der Teilung Null ist (das ist die Modulo-Operation in der Funktion).

Nun ist es aber reichlich sinnlos, 1000 testweise durch 999 zu teilen - das geht sicher nicht ganzzahlig auf. Der Trick, um wesentlich weniger Tests durchführen zu müssen, besteht darin, dass man nicht alle Zahlen prüft, sondern nur bis zur Quadratwurzel der zu prüfenden Zahl. Denn z.B. bei der Zahl 100 wäre die Quadratwurzel 10: 10*10 = 100. Alle anderen Produkte, die auch noch zum Ergebnis 100 führen können, bestehen jeweils aus einer kleineren und einer größeren Zahl als 10. Um herauszufinden, ob 100 eine Primzahl ist, reicht es deshalb aus, nur die kleineren Zahlen bis hin zu 10 zu prüfen - denn da es nur um ganzzahlige Multiplikation geht, hat man damit schon alle Möglichkeiten gefunden.

Deshalb ist die ursprüngliche Schleife bis hin zu <=sqrt($number) vollkommen in Ordnung und wesentlich performanter, weil nur ein wesentlich geringerer Teil der Zahlen geprüft werden muß.

Und als generelle Anmerkung zur Umsetzung der Aufgabe: Es ist immer noch Wahnsinn und sinnloses Verbraten von Rechenleistung, _alle_ Zahlen jeweils _einzeln_ auf ihre Primeigenschaft zu prüfen. Besser wäre da eigentlich, z.B. das Sieb des Erastosthenes anzuwenden: Man beginnt bei 2, die eine Primzahl ist, und streicht alle Vielfachen von 2. Dann kommt 3, und man streicht alle Vielfachen von 3. Die 4 ist gestrichen, nächste Primzahl ist 5 - Streichen aller Vielfachen von 5, und so weiter. Das ist mit Sicherheit schneller.

Auf der Suche nach immer größeren Primzahlen werden wohl allerdings noch ganz andere Methoden angewandt, die ich nicht kenne.

- Sven Rautenberg

[Jan]

Und als generelle Anmerkung zur Umsetzung der Aufgabe: Es ist immer noch Wahnsinn und sinnloses Verbraten von Rechenleistung, _alle_ Zahlen jeweils _einzeln_ auf ihre Primeigenschaft zu prüfen. Besser wäre da eigentlich, z.B. das Sieb des Erastosthenes anzuwenden: Man beginnt bei 2, die eine Primzahl ist, und streicht alle Vielfachen von 2. Dann kommt 3, und man streicht alle Vielfachen von 3. Die 4 ist gestrichen, nächste Primzahl ist 5 - Streichen aller Vielfachen von 5, und so weiter. Das ist mit Sicherheit schneller.

Auf der Suche nach immer größeren Primzahlen werden wohl allerdings noch ganz andere Methoden angewandt, die ich nicht kenne.

Hallo Sven,

stimme ich dir zu. Für diese Aufgabe würde ich zumindest die gesamte Funktion optimieren und den seperaten Aufruf über die while-Schleife streichen. Gefragt wurde aber, wie es möglich ist die Ergebnisse ohne sqrt zu bekommen.

Viele Grüsse
Jan

[Sven Rautenberg]

Moin!

stimme ich dir zu. Für diese Aufgabe würde ich zumindest die gesamte Funktion optimieren und den seperaten Aufruf über die while-Schleife streichen. Gefragt wurde aber, wie es möglich ist die Ergebnisse ohne sqrt zu bekommen.

Wirklich? Ich glaube nicht.

"Warum? wo ist der Unterschied ob man die Quadratwurzel einer Zahl oder die Zahl selbst oder eine ganz normale Zahl nimmt?(Abgehsehen von der Höhe der Zahl, aber dann nur 0 und 1 zu schreiben ist doch auch irgendwie unlogisch)."

- Sven Rautenberg

[MudGuard]

Hi,

Und als generelle Anmerkung zur Umsetzung der Aufgabe: Es ist immer noch Wahnsinn und sinnloses Verbraten von Rechenleistung, _alle_ Zahlen jeweils _einzeln_ auf ihre Primeigenschaft zu prüfen. Besser wäre da eigentlich, z.B. das Sieb des Erastosthenes anzuwenden: Man beginnt bei 2, die eine Primzahl ist, und streicht alle Vielfachen von 2. Dann kommt 3, und man streicht alle Vielfachen von 3. Die 4 ist gestrichen, nächste Primzahl ist 5 - Streichen aller Vielfachen von 5, und so weiter. Das ist mit Sicherheit schneller.

Es ist eine Frage, was Dir wichtiger ist - Speicherplatz oder Rechenleistung.

Eine Mischung erscheint mir ganz sinnvoll:
Man merkt sich die gefundenen Primzahlen.
Und teilt dann nicht mehr durch alle Zahlen von 2 bis sqrt(x), sondern nur durch die gefundenen Primzahlen von 2 bis sqrt(x).
Das reduziert die benötigte Rechenleistung, da nicht mehr sinnlos durch z.B. 4 oder 6 geteilt wird - wenn das ohne Rest möglich wäre, wäre ja schon beim  Teilen durch 2 oder 3 herausgekommen, daß es sich nicht um eine Primzahl handelt.

Auf der Suche nach immer größeren Primzahlen werden wohl allerdings noch ganz andere Methoden angewandt, die ich nicht kenne.

Das ist u.a. davon abhängig, was das Ziel ist:
festzustellen, ob die Zahl x eine Primzahl ist
oder
(irgend)eine Primzahl zwischen y und z zu finden...

cu,
Andreas

[Sven Rautenberg]

Moin!

Eine Mischung erscheint mir ganz sinnvoll:
Man merkt sich die gefundenen Primzahlen.
Und teilt dann nicht mehr durch alle Zahlen von 2 bis sqrt(x), sondern nur durch die gefundenen Primzahlen von 2 bis sqrt(x).
Das reduziert die benötigte Rechenleistung, da nicht mehr sinnlos durch z.B. 4 oder 6 geteilt wird - wenn das ohne Rest möglich wäre, wäre ja schon beim  Teilen durch 2 oder 3 herausgekommen, daß es sich nicht um eine Primzahl handelt.

Klingt gut, ist aber irgendwie nicht umsetzbar.

Entweder lautet die Aufgabe einer Funktion, alle Primzahlen im Intervall von 2 bis x herauszufinden - dann ist ein lineares Abarbeiten des Zahlenbereichst sinnvoll, ebenso das Speichern der Zwischenergebnisse, um diese weiterzuverwenden. Im Prinzip also deine "Mischform" - nur dass diese Mischform eben nichts mischt, sondern das klassische "Sieb" ist.

Oder die Aufgabe lautet, zu einer gegebenen Zahl die Primzahleigenschaft festzustellen. Dann wird man logischerweise von 2 bis sqrt(x) alle Zahlen auf Teilereigenschaft prüfen müssen. Wenn die 2 die Zahl teilt, bricht die Funktion sofort ab, so dass die 4 gar nicht erst geprüft werden muß. Teilt die 2 die zu prüfende Zahl nicht, kommt es sicherlich dazu, dass vielleicht auch mit 4 geprüft wird, was sicherlich unsinnig ist, aber nur verhindert werden könnte, wenn man vorher die Primzahleigenschaft der Zahl 2 festgestellt und daraufhin alle Vielfachen von 2 für die Prüfung gesperrt hätte. Das ist aber doppelt gemoppelt, bzw. wird es hier ziemlich rekursiv: Die Prüfung einer beliebigen Zahl auf Primzahleigenschaft erfordert die Prüfung aller potentieller Teiler auf Primzahleigenschaft, um die Vielfachen der Teiler auszuschließen... da könnte sich die Katze selbst in den Schwanz beißen. Außerdem wäre die Implementation nicht sauber, da die Tabelle, welche Zahlen gesperrt sind, irgendwie zwischen den Funktionsaufrufen weitergereicht werden muß - und das führt dann doch wieder zur Erstellung eines "Siebs".

Allerdings: Eine wirkliche Performance-Verbesserung ist simpel zu realisieren: Als Teiler braucht man im Prinzip nur die 2 zu prüfen und sonst keinerlei geraden Zahlen mehr. Das verdoppelt die Geschwindigkeit grob geschätzt.

- Sven Rautenberg

[romy]

Hi,

// ++++ Funktion zur Ermittlung ob es sich um eine Priemzahl handelt
// in der Schleife guckt er ob es einen Teiler gibt (dann wäre es ja keine Priemzahl)
Allerdings um das Ganze effizient zu machen läuft die Schleife nicht durch alle Zahlen sondern nur durch die Relevanten Zahlen, eben bis Wurzel(zahl), da die darauffolgenden zahlen wieder Teil des Produktes mit Zahlen wären die bis dahin schon aufgetaucht sind.

<?php
function chk_prime($number){
 $prime = true;
 for($i=2;$i<=sqrt($number);$i++){
  if($number % $i == 0){
  $prime = false;
  break;
  }
 }
 if($prime == false):
  return false;
 else:
  return true;
 endif;
}

// ++++ hier machst Du einfach eine Ausgabe der Priemzahlen zwischen 0 und 1000 und rufst Dabei zum check die Funktion auf

$i = 0;
while($i < 1000){
 if(chk_prime($i)){
 echo $i."<br>";
 }
 $i++;
}
?>

wenn ich jezt allerdings das sqrt($number) weglasse, schreib es nur die zahlen 0 und 1.

Das kannst Du nicht weglassen, denn es ist wichtig zur Ausführung der Schleife, was hast Du stattdessen geschrieben? Je nach dem kommt es zur Anzeige von 0 und 1

und wenn ich anstatt sqrt($number) eine zahl (z.B. 900) schreibe,  schreibt das Skript 1 und die Primzahlen ab der definierten Zahl.

Wie gerade beschrieben. Die Anzahl die Du verwendest hat nichts mit der Funktion zu tun.

Hoffe es ist einigermassen verständlich erklärt!?

ciao
romy

[Axel Richter]

Hallo Romy,

Priemzahl
Priemzahl)
Priemzahlen

*g*
Kautabak kauende Zahlen?
http://ingeb.org/Lieder/eshabend.html

Eine Primzahl ist eine Zahl, die nur durch Eins und sich selbst teilbar ist, weshalb sie als primäre Zahl oder Primzahl bezeichnet wird. Im Englischen ist der Wortstamm noch besser erhalten geblieben in: prime number.

viele Grüße

Axel

[romy]

Hi,

Kautabak kauende Zahlen?
http://ingeb.org/Lieder/eshabend.html

pfeifend in die Luft guck...
peinlich peinlich

Naja man denke sich bitte einen Grund aus, warum ich beim Verfassen des Textes nicht in voller Zurechnungsfähigkeit stand. Danke

;););)

ciao
romy

[bjb]

hallo

Dieses Skript funktioniert wunderbar

wenn es hausaufgabe ist würde ich noch die 0 und die 1, die ja bekanntlicherweise keine primzahlen entfernen (if-schleife?)

tschüss bjb

[MudGuard]

Hi,

if($prime == false):
  return false;
else:
  return true;
endif;

das ist das gleiche wie

return $prime;

}
$i = 0;

0 und 1 sind keine Primzahlen.
Also einfach erst ab

$i = 2;

loslaufen.

Oder in der Funktion bei 0 und 1 false zurückliefern.

cu,
Andreas

[Severin]

Hallo,

Also vielen Dank für eure antworten :)

gruß,
Severin