Logik !?

[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