Primzahl-Check: Javascript > Delphi

[alzaimar]

Zitat von alzaimar:

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

EDIT:
Ich würde aber trotzdem das 'Sieve of Atkins' in der Implementierung von negaH nehmen und einfach schauen, ob das entsprechende Bit gesetzt ist. Googel mal danach oder suche hier im Forum. Da gab es vor Kurzem einen lustigen Thread.