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.