Primzahlen-Programm

[Mathematiker]

Hallo,

Zitat von Sir Rufo:

Delphi-Quellcode:

function IsPrime( Value : Int64 ) : Boolean;
...
  // Wir prüfen nicht der Wert selber und auch nicht die 1
  for lIdx := Value - 1 downto 2 do
...

Sorry. Das sollte man auf keinen Fall tun.
Erstens sind kleine Teiler p häufiger Primteiler (Wahrscheinlichkeit 1/p) als große, so dass man von 2 bis zum Endwert prüft und abbricht, wenn die Zahl keine Primzahl ist.
Und zweitens ist der letzte zu testende Wert die (gerundete) Quadratwurzel von value. Alle größeren Teiler sind Komplementteiler von kleineren und deshalb nicht mehr zu überprüfen.

@BlackPegasus: Die Frage ist, in welcher Größenordnung sind die zu testenden Zahlen. Das Primzahlsieb des Eratosthenes (Googeln!) ist immer eine Überlegung wert, da es extrem schnell ist.

Beste Grüße
Mathematiker