Beiträge durchsuchen

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).