Primzahlen noch effektiver berechnen
-
Hallo!
Ich hab eine Funktion geschrieben die prüft ob eine übergebene Zahl eine Primzahl ist. Jetzt will ich die auch für z.B. 2^31 (integer) benutzen, nur dauert das Ewigkeiten. Könnte an meiner primitiven Umsetzung liegen (Ich gehe alle Zahlen durch und wenn ich vorher einen Teiler finde breche ich ab).
Jetzt die Preisfrage: Lohnt es sich da irgendwas ganz kompliziertes zu implementieren oder dauert die Berechnung bei z.B. 2^31 auch bei einem effektierem Algrithmus 3 Stunden?
-
http://de.wikipedia.org/wiki/Primzahlen
da gibts auch links zu besseren algorithmen
-
antwort auf deine preisfrage: ja die implementierung lohnt sich. das sollte bei einer geschickten implementierung eher im ms- oder s-bereich liegen.
ansonsten der für dich wichtige link ist wohl eher dieser: http://de.wikipedia.org/wiki/Primzahltest