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