Delphi errechnet keine Primzahlen größer als 5000

[Furtbichler]

Und dann ist das noch so, das alle Primzahlen > 3 der Form 6n+/-1 sind. Also kann man alle Primzahlen so prüfen

Delphi-Quellcode:

// 2,3 => Primzahl
p := 5;
repeat
  If IsPrime(P) then AddToPrimeList(P);
  If IsPrime(P+2) then AddToPrimeList(P+2);
  inc(P,6);
until p>maxint-6; // oder so ähnlich

Und die Funktion IsPrime prüft nicht bis Wert/2, sondern nur bis Sqrt(Wert) und da auch nur mit allen bisherigen Primzahlen, also:

Delphi-Quellcode:

Function IsPrime (P : Integer): Boolean;
Begin
  MaxP := Trunc(Sqrt(P));
  I := 0;
  While (Primes[I]<MaxP) do 
    If P Mod Primes[I]<>0 then 
      exit(false) 
   else 
      inc(I);
  exit(true)
End;

Ist aber ungetestet.

Und noch eigentlicher verwendet man 'Sieve of Atkin' oder 'Sieve of Eratosthenes'. Da bekommt man dann alle Primzahlen < 2^31 in so 1-2 Sekunden, wenn ich mich richtig erinnere.