Bei mir erscheint auch der Test mit 2147483647 ohne Verzögerung (also nach 0ms). Allerdings benutze ich ein anderes Verfahren:
Ich prüfe nicht alle Zahlen bis N / 2, sondern nur bis s=Sqrt(N). Denn eine Zahl N kann nur Primfaktoren haben, die <=s sind.
Dann kann man noch die Tatsache ausnutzen, das für alle Primzahlen P > 3 gilt: P modulo 6 = 1 oder 5.
Delphi-Quellcode:
Function IsPrime (aNumber : Int64) : Boolean;
(********************************************************************
* Ist aNumber eine Primzahl? Benutzt die Tatsache, das für alle *
* Primzahlen p > 3 gilt : p mod 6 = 1 oder 5. *
* *
* Das hier ist nicht der schnellste Algorithmus, aber lustig isser *
********************************************************************)
Var
iTest, iStop : Int64;
Begin
Result := False;
If aNumber < 2 Then Exit;
if aNumber in [2,3,5] Then Begin
Result := True;
Exit;
End;
If aNumber mod 6 in [0,2,3,4] Then Exit; // Not a prime
If aNumber mod 2 = 0 Then Exit;
If aNumber mod 3 = 0 Then Exit;
If aNumber mod 5 = 0 Then Exit;
iStop := Trunc (0.5 + Sqrt(1.0*aNumber));
iTest := 7;
While iTest < iStop do begin
If aNumber mod iTest = 0 Then Exit;
inc (iTest,2);
If aNumber mod iTest = 0 Then Exit;
inc (iTest,4);
End;
Result := True;
End;
Beispielperformance (AMD 64):
- Test von 4294967294000017 (is wohl eine Primzahl) dauerte 7985 ms