Sehr schneller Primzahl-Finder

[GTA-Place]

Auch euch will ich meinen Source nicht vorbehalten:

Delphi-Quellcode:

function Prim(Zahl: Cardinal): Boolean;  
var  
  Teiler: PCardinal;  
  Wurzel: Cardinal;  
begin  
  Result := True;    // Result = True  
  if not odd(Zahl) OR (Zahl <= 5) then    // Ist die Zahl nich ungerade oder kleiner als 5, dann  
  begin  
    if (Zahl <> 2) AND (Zahl <> 3) AND (Zahl <> 5) then    // Ist die Zahl nicht 2 und nicht 3 und nicht 5, dann  
      Result := False;    // Result = False  
    Exit;                 // Exit  
  end;  
  Teiler := @PrimS[0];    // Teiler = @PrimS[0]  
  Wurzel := Trunc(sqrt(Zahl));    // Wurzel aus der Zahl  
  while Teiler^ <= Wurzel do    // Solange Teiler^ <= Wurzel ist, mache  
  begin      
    if Zahl mod Teiler^ = 0 then    // Ist Zahl / Teiler^ = Rest 0, dann  
    begin  
      Result := False;    // Result = False  
      Break;    // Break  
    end;  
    Inc(Teiler);    // Teiler erhöhen um 1  
  end;  
end;

Delphi-Quellcode:

procedure TMainForm.StartButClick(Sender: TObject);  
var  
  Start, Ende: Real;  
  Z: PCardinal;  
  X, LPrim: Cardinal;  
  PrimF: TStringList;  
begin  
  try  
    Von := StrToInt(VonEdit.Text);    // Start  
    Bis := StrToInt(BisEdit.Text);    // Endwert  

 
    if Bis > 10 then  
      SetLength(PrimS, Trunc(0.4*Bis-(Bis/4)))    // Größe des Array: 0.4*Bis-(Bis/4)  
    else  
      SetLength(PrimS, 4);  

 
    LPrim := 0;    // Letze Prim = 0  
    Z := @PrimS[0];     // Gefundene Prims = 0  

 
    if (Von >= 0) AND (Bis >= 0) AND (Von < Bis) then    // Von >= 0; Bis >= 0; Von < Bis;  
    begin  
      Start := GetTickCount;    // Start-Zeit  

 
      for X := Von to Bis do    // Schleife: Startwert -> Endwert  
      begin  
        if Prim(X) then    // Funktion ausführen, wenn Prim dann  
        begin  
          Z^ := X;    // Prim in Array schreiben  
          Inc(Z);    // Z erhöhen um 1  
          LPrim := X;    // Letze Prim = X  
        end;  
        if X mod 20000 = 0 then    // Wenn X : 20.000 = Rest 0, dann  
        begin  
          Application.ProcessMessages;    // Anwendung aktualisieren  
          PrimLab.Caption := 'Aktuelle Primzahl: ' + IntToStr(LPrim);    // Akt. Primzahl anzeigen  
        end;  
      end;  

 
      Ende := GetTickCount;    // End-Zeit  
      DauerLab.Caption := 'Diese Überprüfung hat ' + FloatToStr((Ende - Start) / 1000) + ' Sekunden gedauert.';    // Dauer anzeigen  

 
      PrimLab.Caption := 'Speichern...';    // "Speichern..." anzeigen  

 
      Z := @PrimS[0];    // Z auf 0 stellen  
      PrimF := TStringList.Create;    // Stringlist erzeugen  

 
      for X := 0 to Length(PrimS)-1 do    // Von 0 bis Größe des Array  
      begin  
        if Z^ = 0 then    // Wenn Z^ = 0, dann  
          Break;    // Break  
        PrimF.Add(IntToStr(Z^));    // Prim in Stringlist schreiben  
        Inc(Z);    // Z erhöhen um 1  
      end;  

 
      PrimF.SaveToFile('Prim.txt');    // Stringlist speichern  
      PrimF.Free;    // Stringlist freigeben  

 
      PrimLab.Caption := 'Aktuelle Primzahl: ' + IntToStr(LPrim);    // Akt. Primzahl anzeigen  
    end  
    else  
      ShowMessage('Ungültige Eingabe(n)!');    // Bei falschen Eingaben, Nachricht anzeigen  
  except  
    ShowMessage('Es ist ein Fehler aufgetreten!');    // Wenn Fehler auftritt, Nachricht anzeigen  
  end;  
end;

Das Programm überprüft 10.000.000 Zahlen in erstaunlichen 6 Sekunden.
Und das Speichern geht so schnell, dass man "Speichern..." gar nicht sieht.

[pirechner]

tag auch
ich befasse mich jetzt auch schon etwas länger mit primzahl berechnung/ findung.
WEgen der unglaublichen schnelligkeit wollte ich jetzt mal fragen wie viel hz dein rechner hat?
meiner hat bescheidene 392mhz und schaft mit meinem code in sechs sekunden 120.000 primzahlen zu finden.

Code:

procedure tprimzahlen.findeprimzahlen;
var lauf: int64;
    //laufzwei: integer;
    wurzelderletztenprz : extended;
begin
  repeat
    lauf:= 2;
    wurzelderletztenprz:= sqrt(speicherarray[anzahlprimzahlen]);
      repeat
        hilf:= speicherarray[lauf];
        inc(lauf);
        if zahl mod hilf = 0  //zahl ist keine primz weil sie einen teiler hat
        then begin
          zahl:= zahl + 2; //hier passiert das gleiche wie wenn es eine primzahl wäre
          lauf:= 2;        //bloß das keine zahl geschrieben wird und die zahl damit übergangen wird
          wurzelderletztenprz:= sqrt(speicherarray[anzahlprimzahlen]);
        end
       until  hilf -1 > wurzelderletztenprz; //brauch nur bis zur hälfte danach ists sinnlos
      inc(anzahlprimzahlen);
      speicherarray[anzahlprimzahlen]:= zahl;
      application.ProcessMessages;
    zahl:= zahl + 2;
  until stop = true;
end;

verlangsamt wird bei mir die ganze sache durch application.processmessages ohne die mein programm aber logischer weise nicht mehr aus der repeat-schleife käme.

p.s. kann es sein dass du nur überprüfst ob die zahlen durch zwei, drei und fünf teilbar sind?

[axelf98]

Zitat:

Zitat von GTA-Place

Delphi-Quellcode:

 PrimLab.Caption := 'Speichern...';    // "Speichern..." anzeigen

Das Programm überprüft 10.000.000 Zahlen in erstaunlichen 6 Sekunden.
Und das Speichern geht so schnell, dass man "Speichern..." gar nicht sieht.

Hmm, schieb' mal ein

Delphi-Quellcode:

Application.ProcessMessages;

dahinter, dann siehst du auch das Speichern...

[GTA-Place]

@pirechner:

1. AMD Athlon XP 2600+
2. Nein, ich prüf erst du 2, 3 und 5 und dann nur durch die gefunden Primzahlen

@axelf98

Jo habs bemerkt.

[pirechner]

ja das mache ich genauso in meinem array befinden sich bereits die 2 , 3 und 5 auch wenn das aus dem code schnipsel nicht deutlich wird.

[idontwantaname]

hi

wäre jemand so nett und könnte mir ein sample schicken?
oder mir sagen, was die ganzen variablen zu bedeuten haben (die, die nicht in der procedure/function deklariert werden)

danke

[GTA-Place]

Delphi-Quellcode:

var
  PrimS: Array of Cardinal;
  Von, Bis: Integer;

[sakura]

Hi GTA,

was Du da hast ist nicht unbedingt ein Programm um schnell Primenzahlen zu finden. Dazu gibt es weit bessere Algorithmen. Der Algorithmus, welchen Du da aufzeigst, dient zur Überprüfung, ob eine gegebene Zahl X eine Primzahl ist, dieser ist allerdings nicht sonderlich brauchbar um mehrere zu finden.

Mein Lieblingsalgorithmus findest Du im Projekt im Anhang, das Sieb des Erasthothes od so :gruebel: Alle Primzahlen zw. 1 und 10.000.000 findet der Algorithmus bei mir in weniger als 1,5 Sekunden ;-)

...:cat:...

@Ulti: Danke, Sieberfinder korrigiert ;-)

[sakura]

Da fällt mir noch was auf. Und sorry, wenn das jetzt hart klingt, aber es ist wahr: Deine Kommentare sind genauso viel wert, wie die in meinem Beispiel (da sind keine). Ein Kommentar soll nicht Zeile für Zeile die aktuelle Zeile erklären sondern eher einen Code-Abschnitt kurz erläutern ;-)

...:cat:...

[Ultimator]

@Sakura: Der Typ hieß Erastosthenes ;-)

Ich weiß zwar, dass er so heißt, aber nicht wie er geschrieben wird :mrgreen:

PS:@GTA-Place: Fairerweise solltest du dazu sagen, dass dir an diesem Code viele Mitglieder des DF geholfen haben ;-)