Zahl auf Primzahl prüfen

[Lyan]

Hallo...

ich habe eine Form die per Knopfdruck Zahlen von 1-100 aausgibt. Also man kann in einer Radiogroup auswählen ob man z.B nur gerade Zahlen ausgegeben haben möchte oder nur ungerade oder alle zahlen... jetzt würde ich gerne eine überprüfung durchgehen die mir sagt ob es eine Primzahl ist!.


Ein Beispiell war das hier:

Code:

2: begin    // Case index 2 (UNGERADE ZAHLEN)
        if checkboxnachrechts.Checked AND checkboxnachunten.checked then
         ShowMessage('Bitte wählen sie nur eine Checkbox aus!')
        else
        begin
          if checkboxnachunten.Checked then
          begin
            i := 1;
              repeat
                inc(i, 2);
                memozahlen.Lines.Add(inttostr(i));
              until (i >= 100);
          end
          else
          begin
            if checkboxnachrechts.checked then
            begin
              i := 1;
              while i < 98 do
              begin
                inc(i, 2);
                s := s + inttostr(i);
                if i <> 99 then
                  s := s + ', ';
              end;
             memozahlen.Lines.Add('1, ' + s);
            end;
          end;
        end;
       end;

(Das war das Beispiel für ungerade Zahlen)

Jemand ne idee?

[Klaus01]

Hallo,

DeddyH hatte im Forum mal diese Funktion gepostet:

Delphi-Quellcode:

function isprime(a: integer): Boolean; //soll testen ob a eine Primzahl ist
var Teiler: integer;
begin
  Result := a > 1;
  Teiler := Pred(a);
  while Result and (Teiler > 1) do
    begin
      Result := a mod Teiler <> 0;
      dec(Teiler);
    end;
end;

Grüße
Klaus

[DeddyH]

Das ist allerdings die "Hausfrauenvariante" und extrem lahmarschig, auf der anderen Seite leicht nachzuvollziehen. Wenn es schneller sein soll, empfehle ich die DP nach anderen "IsPrime"-Implementierungen zu durchsuchen, da müsste es einige geben.

[Aphton]

Man kann zb. den kleinen fermatschen Satz hernehmen.

a^(p-1) mod p = 1

Bedingungen:
- a: integer; kein Vielfaches von p -> 1 < a < p
- p: Primzahl

Test: Primzahl

Code:

p = 13
a = 2

2^12 mod 13 = 1
4096 mod 13 = 1
1 = 1

p = Primzahl

Test: ungerade Zahl

Code:

p = 15
a = 2

2^14 mod 15 = 1
16384 mod 15 = 1
4 = 1

p <> Primzahl

Delphi-Quellcode:

function binPowMod(Base, Exponent: Int64; const ModVal: Int64): Int64;
begin
  Result := 1;
  while Exponent > 0 do
  begin
    if Exponent and 1 > 0 then
      Result := (Result * Base) mod ModVal;
    Base := Base * Base;
    Exponent := Exponent shr 1;
  end;
end;

function isPrime(const P: Int64): Boolean;
begin
  Result := (P > 1) and (P and 1 > 0) and (binPowMod(2, p-1, p) = 1);
end;

Edit:
Huch, habe die 64 Bit Grenze nicht berücksichtigt... Falls man aber eine BigInteger Klasse benutzt, sollte das kein Problem mehr werden.

[Codewalker]

Mit dem Fermat muss man vorsichtig sein, wie man ihn einsetzt: Man kann damit nur zeigen, dass eine Zahl i keine Primzahl ist, also einen Gegenbeweis finden. Die Umkehrung gilt nicht (genauer: Sie gilt nicht für alle Carmichael-Zahlen wie 561, 1105, usw)!

Je nachdem um was es geht reicht aber auch ein probabilistischer Primzahltest. Mit diesem macht man eine bestimmte Anzahl Iterationen und kann dann mit einer gewissen Genauigkeit sagen, dass eine Zahl i eine Primzahl ist (oder halt exakt sagen, dass sie keine ist, wenn man einen Teiler findet). Nimmt man beispielsweise den Miller-Rabin-Test (ist nicht allzu aufwändig zu implementieren), so hat man nach 33 Iterationen eine Fehlerquote < 10^⁻100 (d.h. man kann 10^100 Primzahlen auf diese Weise ermitteln und macht statistisch dann den ersten Fehler. Da ist mehr als es Atome im Universum gibt, dürfte aber reichen). Wenn man eine brauchbare BigInteger-Unit nimmt, ist die Rechnung auch ordentlich performant.

Wenn es bei den vom TE genannten kleinen Zahlen bleibt, ist aber auch ein stures durchprobieren aller Teiler immer noch hinreichend schnell.

@DeddyH: Du fängst in deinem Code bei

Delphi-Quellcode:

Pred(a)

an, was unnötig ist. Damit es ein Teiler ist, kann er ja maximal halb so groß sein wie a. Man kann auch zeigen, dass es reicht bis zur Quadratwurzel von a durchzuprobieren. Damit sparst du nochmal etliche Durchläufe.

[DeddyH]

Ich hab ja gesagt, dass die Lösung keinesfalls optimiert ist. Man kann ja z.B. auch im Vorfeld prüfen, ob a eine gerade Zahl > 2 ist, die kann man auch von vornherein ausschließen. Aber als ich den Code schrieb, ging es wohl auch nicht um Geschwindigkeit, sondern mehr um das Verständnis.