Nicht-Primzahl-Test nach Fermat

[CalganX]

(Für mathematischen Hintergrund und Beweis, siehe Wikipedia)

Delphi-Quellcode:

uses Math;

{a ist eine beliebige Zahl zwischen 1 und n-1; n ist zu testende Zahl}
function IsNotPrime(const a, n: longint): boolean;
begin
  Result := (Round(Power(a, n-1)) mod n) <> 1;
end;

Wichtig: Wenn diese Funktion false zurückgibt, heißt das nicht, dass n eine Primzahl ist. Es ist lediglich eine Pseudo-Primzahl.