Primzahlen-Programm

[Sir Rufo]

Zitat von 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.

I know

Ich wollte in dem Quelltext die Vorüberlegung

Zitat:

Wenn diese nur durch sich selbst oder 1 ohne Rest teilbar ist.

quasi 1:1 reinbringen.

Als Lerneffekt: Eigentlich programmiere ich so, wie man denkt/spricht/schreibt.

Die gerundete Quadratwurzel als Maximum und mit dem kleinesten Wert beginnen ist dann Performance-Optimierung.

Also nach dem Motto:

Zitat:

1. Make it work
2. Make it fast