Primzahlen erkennen
Definition
Eine Primzahl ist eine natürliche Zahl mit genau zwei natürlichen Zahlen als Teiler, nämlich der Zahl 1 und sich selbst (siehe Wikipedia). Eine natürliche Zahl ist in diesem Fall eine positive ganze Zahl.
Umsetzung
Diese Funktion prüft, ob die angegebene Zahl (ANumber) eine Primzahl ist:
function IsPrime(ANumber: Cardinal): Boolean;
var
DivCount: Integer;
Divisor: Cardinal
begin
DivCount := 0;
if (ANumber > 0) then
begin
for Divisor := 1 to ANumber do
begin
if (ANumber mod Divisor) = 0 then
Inc(DivCount);
if (DivCount > 2) then
Break;
end;
end;
Result := (DivCount = 2);
end;
Dabei wird festgestellt, wie viele Teiler ANumber hat, indem durch jede mögliche Zahl geteilt wird. Ergibt die Division keinen Rest, ist der Divisor ein Teiler der Zahl.Gibt es am Ende genau zwei Teiler, ist die Zahl prim.Die Funktion kann beispielsweise so aufgerufen werden:
procedure TForm1.Button1Click(Sender: TObject);
begin
if IsPrime(4) then
ShowMessage('prim')
else
ShowMessage('nicht prim');
end;
Optimierung
Ein Problem bei dieser Funktion ist aber die lange Laufzeit:Diese kann noch deutlich verbessert werden, indem einige Optimierungen durchgeführt werden.Ist eine natürliche Zahl N durch eine natürliche Zahl a teilbar, gibt es eine Zahl b, sodass gilt:N = a * bUm zu prüfen, ob N eine Primzahl ist, müssen für a alle Zahlen von 2 bis N-1 eingesetzt werden. Ergibt sich ein b, bzw ist N durch a teilbar, ist die Zahl keine Primzahl und die Suche kann abgebrochen werden.Wenn N durch a teilbar ist, ist N auch durch b teilbar. Da die Faktoren a und b vertauscht werden dürfen, muss nur solange geprüft werden, bis a >= b ist. a ist dann die Wurzel von N.Es muss also nur geprüft werden, ob N durch die Zahlen von 2 bis zur Wurzel von N teilbar ist.
Alle Zahlen, die durch a * b teilbar sind, sind auch durch a und b teilbar.Um festzustellen, ob N eine Primzahl ist, muss also nur durch Zahlen geteilt werden, deren Faktoren noch nicht durch N geteilt wurden. Da die Suche ab 2 beginnt, sind das nur solche Zahlen, die keinen Faktor haben, der größer gleich 2 ist, als auch Primzahlen.Um N auf Teilbarkeit zu prüfen, muss also nur durch alle Primzahlen geteilt werden, die kleiner als N sind.Das Problem hierbei ist, dass es sehr aufwendig ist, Primzahlen zu suchen.Der Einfachheit halber werden alle geraden Zahlen, die größer als 2 sind, übersprungen: selbst dadurch verdoppelt sich schon die Geschwindigkeit der Ausführung, da genau die Hälfte alle natürlichen Zahlen gerade ist.
Mit Hilfe dieser Optimierungen ergibt sich dann folgende Funktion:
function IsPrime(ANumber: Cardinal): Boolean;
var
Divisor: Integer;
begin
Result := (ANumber = 2) or ((ANumber > 1) and (ANumber mod 2 <> 0));
if (not Result) then
Exit;
Divisor := 3;
while (Divisor < sqrt(ANumber) + 1) do
begin
if (ANumber mod Divisor = 0) then
begin
Result := False;
Exit;
end;
Inc(Divisor, 2);
end;
end;
Hinweis: Auch diese Funktion eignet sich nur für kleinere Zahlen. Bei größeren Zahlen, beispielsweise für Verschlüsselungen, sollten andere Verfahren vorgezogen werden (z.B. der Rabin-Miller-Test).