Eines wunderschönen Mittags unterhielt ich mich mit DEM Meisterprogrammierer und Architekt unserer Firma, Harmen, bezüglich der Prüfung der ungeraden Zahlen auf Primeigenschaften. Seine Idee war, daß ich die ungeraden Zahlen nur gegen die bereits errechneten Primzahlen prüfen müßte. Und da hat er Recht!
Jede andere ungerade Zahl (keine Primzahl) wäre doch eigentlich nur noch der Multiplikator zweier Primzahlen. Das ist doch schon mal ausgezeichnet, weniger Zahlen zum durchlaufen. Bei 1000 Zahlen sind es anstatt 499 nur noch 168, bei einer Million nur noch 78498. Perfekt!
Wenn man das jetzt weiter denkt, könnte man argumentieren, daß man nur gegen Primzahlen prüfen sollte, die maximal die Quadratwurzel der zu prüfenden ungeraden Zahl groß sind. Das macht aus folgendem Grund Sinn:Ist die zu prüfende ungerade Zahl keine Primzahl, wäre sie spätestens mittels x*y bis zu ihrer Quadratwurzel gefunden worden. Hat man noch nichts gefunden, ist es eine Primzahl.
Beispiel:
Zu prüfenden Zahl: 21
Quadratwurzel aus 21: 4.58
Teiler durch Primzahlen: 21 / 1 = 21, 21 / 3 = 7 (Teiler gefunden, keine Primzahl)
Zu prüfenden Zahl: 23
Quadratwurzel aus 23: 4.8
Teiler durch Primzahlen: 23 / 1 = 23, 23 / 3 = 7.67 (Teiler nicht gefunden, Primzahl)
Noch mehr Freude herrschte, als dies meinen Kopf durchstreifte. Prompt wurde es in meinen Code implementiert. Mit Erschrecken stellte ich Fest, dass die Berechnung bis zu einer Million plötzlich auf 9 Minuten stieg. Seltsam, sollte doch jetzt noch schneller sein, weil bei 1000 Zahlen (Quadratwurzel = 31,6) nur noch gegen 11 Zahlen geprüft werden müssten. Bei einer Million (Quadratwurzel = 1000) nur noch gegen 168 anstatt 78498 Zahlen.
Nach Geschwindigkeitsmessungen der for-Schleife bis zu einer Million (for (i = 0; i < 1000000; i++)) und der Quadratwurzel von einer Million (sqrt(1000000)) hat sich herausgestellt, dass die Quadratwurzel Funktion sqrt ca. 15 Mal langsamer ist als die unnötig in die Länge gezogene for-Schleife.
Nun gilt es auch noch nach einer schnelleren Methode zu suchen eine Quadratwurzel ziehen zu können. What a pitty :-/