Die Idee mit dem Sieb von Eratosthenes kam mir auch. Da ich aber konsequent maximal einen Joke pro Woche poste, liess ich es bleiben.
Die Woche ist vorüber:
Anderer Vorschlag. Lies dich ein wenig hier ein (oder weiterführend z.Bsp. Artins kleines und feines Buch über Galois Theorie):
https://de.wikipedia.org/wiki/Endlic...er_Logarithmus
Daraus kannst du schliessen: Wenn du prüfen willst, ob eine natürliche Zahl q>1 eine Primzahl ist, dann berechne
a^(q-1) modulo q für alle a in {1,2,...q-1}
Wenn das immer 1 ergibt, dann ist q eine Primzahl.
Delphi-Quellcode:
function istprim( q : integer ) : boolean;
var a, i, pot : integer;
begin
Result := false;
if q < 2 then exit;
for a := 1 to q-1 do
begin
pot := 1;
for i := 1 to q-1 do pot := (pot*a) mod q;
if pot <> 1 then exit;
end;
Result := true;
end;