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

[idontwantaname]

@sakura:
ich weiß nicht wieso, aber wenn ich dein beispiel öffne, hängt sich delphi auf :gruebel:

[sakura]

Zitat:

Zitat von idontwantaname

@sakura:
ich weiß nicht wieso, aber wenn ich dein beispiel öffne, hängt sich delphi auf :gruebel:

Müssen wohl 2005 Bugs drinne sein... Keine Ahnung, bei mir gehts. In D7 und D2005.

In D5 musst Du die Unit Variants löschen.

...:cat:...

P.S.: Die Reihenfolge der schnellsten Compilate: D2005, D5, D7

[mirage228]

Zitat:

Zitat von sakura

P.S.: Die Reihenfolge der schnellsten Compilate: D2005, D5, D7

D2005 ist schneller als D5, das den angeblich Compiler mit der besten Optimierung hat? :shock:

mfG
mirage228

[GTA-Place]

Die Kommentare stehen nicht im Prog drin.
War nur für hier, damit man sie versteht.

[sakura]

Zitat:

Zitat von mirage228

D2005 ist schneller als D5, das den angeblich Compiler mit der besten Optimierung hat? :shock:

In diesem Fall ja :-)

...:cat:...

[sakura]

Zitat:

Zitat von GTA-Place

War nur für hier, damit man sie versteht.

Wo tragen folgende Beispiele zum Verständnis bei :gruebel:

Delphi-Quellcode:

Result := True;    // Result = True  
  if not odd(Zahl) OR (Zahl <= 5) then    // Ist die Zahl nich ungerade oder kleiner als 5, dann  
...
      Result := False;    // Result = False  
    Exit;                 // Exit  
...
  Teiler := @PrimS[0];    // Teiler = @PrimS[0]  
  Wurzel := Trunc(sqrt(Zahl));    // Wurzel aus der Zahl  
...

...:cat:...

[GTA-Place]

Hab einfach mal alles kommentiert.
Wie gesagt, im Prog. ist das net.

[Nicodius]

naja .. also wenn ich die dpr öffne stürzt mein liebes delphi ab ... liegt das an delphi 2005 das du beitzt?

... sonst geht alles .. aber wenn ich das jetzt öffne - absturz

[sakura]

Zitat:

Zitat von Nicodius

naja .. also wenn ich die dpr öffne stürzt mein liebes delphi ab ... liegt das an delphi 2005 das du beitzt?

Nein, eigentlich nicht. Wie gesagt, selbst D5 öffnet es ;)

...:cat:...

[Nicodius]

kmisch ich kann alles bis auf den source von dir öffnen :gruebel:

[fkerber]

Hi!

Bei mir kommt mit D7 aber auch ein hässlicher Fehler:
Out of Memory

Dann passiert nichts mehr.


Mit D2005 geht es.



Ciao Frederic

[MagicAndre1981]

@sakura

bei mir stürtzt Delphi auch mit der Fehlermeldung "Out of memory" ab. Dabei habe ich doch 1,25GB RAM.
:gruebel:

Hast du eine Ahnung woran das liegt?

:gruebel:

MagicAndre

[MagicAndre1981]

@fkerber und alle mit dem D7 Fehler.

Ich habe einfach die dsk und cfg - Datei gelöscht und schon konnte ich es öffnen. :-D

Gruß MagicAndre

[fkerber]

Hi!

Zitat:

Zitat von MagicAndre1981

Ich habe einfach die dsk und cfg - Datei gelöscht und schon konnte ich es öffnen. :-D

Stimmt!
Sieht man sich die Dateien mal an, ist es wohl kein Wunder - ein Haufen absoluter Pfade auf D2005 und sonstige D2005-spezifische Sachen, anscheinend hat D7 dann da ein paar Probleme.


Ciao Frederic


P.S.: Das D7-Kompilat war bei mir 0,04 Sekunden schneller als das von D2005

[mirage228]

Hi,

ich hatte bei D7 auch erst:

Zitat:

Zitat von D7

---------------------------
Fehler
---------------------------
Zu wenig Arbeitsspeicher.
---------------------------
OK
---------------------------

wonach die ganzen IDE Fenster "maximiert" waren. Danach hagelte es Zugriffsverletzung, aber ich konnte das Programm doch noch starten :mrgreen: (Scheint so, als würde D7 nicht mit den Fenstergrößen-Einstellungen von D2005 zurechtkommen).

mfG
mirage228

Edit: Bei Delphi 3 sind ganzen IDE Fenster beim Start auch "maximiert" - Das Projekt lässt sich dort aber nicht kompilieren.
(TLargeInteger wird zwar als Int64 ersatz akzeptiert, aber ich weiss nicht, wie ich mit dem Record rechnen soll :-\)

mfG
mirage228

[supermuckl]

solche speedtests würd ich eh sehr oft machen und dann einen mittelwert ziehen.. und das bei jedes mal gleichen einstellungen des zu testenden algos

sonst kommen da die "einsteuungen" von windows mit rein, die andere prozesse verursachen usw :)

[Nicodius]

jap ohne die zwei gehts!


1,72 sec wow

[Nicodius]

wäre super qürdest du den code erklären sakura .. :)

[stoxx]

darf man mal fragen, wozu man die Primzahlen in der Praxis gebrauchen könnte ?
Ist zwar schön, sie zu berechnen, habe sie aber mein ganzes Leben lang noch nicht gebraucht.
Danke ! .. vielleicht tun sich ja ganz neue Möglichkeiten für mich auf ! ;-)

[Luckie]

In der Kryptologie spielen sie eine große Rolle zum Beispiel.

[Nicodius]

ho viele Verschlüsselungsysteme bauen wie Luckie es sagt auf Primzahlen auf!

[Luckie]

Zitat:

Zitat von Luckie

In der Kryptologie spielen sie eine große Rolle zum Beispiel.

Zitat:

Zitat von Nicodius

ho viele Verschlüsselungsysteme bauen wie Luckie es sagt auf Primzahlen auf!

Hat das jetzt einen tiefern Sinn, dass du eine Stunde später das nachplapperst, was ich schon gesagt habe, ohne dem schon gesagten weiters hinzuzufügen?

[sakura]

Zitat:

Zitat von MagicAndre1981

Ich habe einfach die dsk und cfg - Datei gelöscht und schon konnte ich es öffnen. :-D

Ich werde das mal an die Borländer durchreichen :roll: Ist schon seltsam wie man so auf Bugs stößt...

...:cat:...

[sakura]

Zitat:

Zitat von Nicodius

wäre super qürdest du den code erklären sakura .. :)

Nicht wirklich gerne, suche mal im Internet nach dem Namen des Algorithmus: Sieb des Eratosthenes, der wird oft genug erklärt ;-)

...:cat:...

[Phantom1]

Ich habe eben auch nochmal einen neuen Code nach dem SIEB DES ERATOSTHENES geschrieben:

für 10 Mio testzahlen braucht mein Code etwa 0,65 Sekunden (ohne speichern)

Delphi-Quellcode:

procedure SavePrimes(MaxPrime: Cardinal; const FileName: String = '');    
var
  isPrime: Array of Boolean;
  Wurzel, i, j: Cardinal;
  SL: TStringList;
begin
  SetLength(isPrime, MaxPrime+1);
  FillChar(isPrime[2], Length(isPrime)-2, 1);
  Wurzel:=Trunc(Sqrt(MaxPrime));
  for i:=2 to Wurzel do
    if isPrime[i] then begin
      j:=i*2;
      while j<=MaxPrime do begin
        isPrime[j]:=False;
        Inc(j, i);
      end;
    end;

  if FileName<>'' then begin
    SL:=TStringList.Create;
    for i:=2 To MaxPrime do
      if isPrime[i] then
        SL.Add(IntToStr(i));
    SL.SaveToFile(FileName);
    SL.Free;
  end;
end;

[negaH]

:) ist alles relativ. Mein Primzahl Sieb erzeugt alle Primzahlen < 2^32 in 13 Sekunden auf einem P4 1,5MHz und erzeugt sogar noch eine Lookup Table von 630 Mb auf Platte. Das sind also 203.280.221 Primzahlen bis 4.294.967.296 in 13 Sekunden.

Wesentlich ist dabei was ganz anderes: Angenommen du sollst alle Primzahlen zwischen 1.000.000 und 2.000.000 berechnen dann würde dein Verfahren auch die Primzahlen < 1.000.000 berechnen müssen. Ein 8/30 Comb Sieb wie ich es benutze kann aber direkt diese Primzahlen berechnen.

Mal als Vergleich: alle Primes bis 10Mio auf einem P4 mit 1.5GHz werden in 60 Millisekunden berechnet.

Das Problem mit Eratosthenes ist das der Algorithmus enorm viel Speicher verbraucht wenn man bis 2^32 berechnen möchte. Das ist meistens so viel Speicher das der Algorithmus auf heutigen Rechnern inpraktikabel ist. Desweiteren muß der Algorithmus immer alle Primes von 2 angefangen berechnen umdie Nachfolgerprimes berechnen zu können. Eine Ausschnittsberechnung wie beim 8/30 Comb Sieve ist damit nicht möglich. Das Sieb selber verbraucht ca. 256Kb an Speicher.

Gruß Hagen

[dizzy]

Zitat:

Zitat von negaH

in 13 Sekunden auf einem P4 1,5MHz

Das is ne Leistung :mrgreen:

[gordon freeman]

Zitat:

Zitat von negaH

(...) Eine Ausschnittsberechnung wie beim 8/30 Comb Sieve (...)

Wo bekomme ich denn 'nen Code für so'n Comb Sieve? hab ma gegoogelt, aber nix gefunden....

thx, gordon

[negaH]

Gute Frage, ich weis das es im WEB Erklärungen zum Sieb gibt, aber wo kann ich dir auch nicht mehr sagen.Es handelt sich bei dem Algorithmus um ein Sieb das mit den Quadratischen Resten zu den kleinen Primzahlen bis 2^16 arbeitet. Es arbeitet also mit Modularen Ringen -> modulo. Dabei schreitet das Sieb die Zahlen in Schritten von 30 ab und führt dazu 8 Subsiebe zu den ersten Primzahlen mit deren quadratischen Resten mit. Dies ermöglicht es in 8 Bits 30 Zahlen zu speichern und erklärt so den geringen und linearen Speicherbedarf des Siebes. Da man eine Tabelle mit den Quadaratischen Resten direkt zu einem gewählten Startwert initialisieren kann, ist es nun auch möglich mit beliebigen Zahlenbereichen die Berechnungen zu beginnen.

Ich habe mal meinen Source angehngen. Er dient als Anschauung und darf nur mit meiner vorherigen Zustimmung weiterverbreitet werden.

Nun noch einige Erklärungen zum Source.

Die Basis stellt das Object TSmallPrimeSieve dar das immer über die Funktion "Primes" angesprochen werden sollte. Damit ist dieses Object und seine Daten global für die Anwendung verfügbar. Man kann aber auch eigene lokale Kopien erzeugen was aber dann bedeutet das durch die nötigen Neuberechnungen Performance verloren geht.

TSmallPrimeSieve enthält nun einige wichtige Methoden:

.Property Prime[Index]: Cardinal;
gibt die Primzahl mit Index zurück. Die Zahl 2 hat Index 0, 3 hat Index 1, 5 hat Index 2, 7 hat Index 4 usw. usw.

.IndexOf(Value: Cardinal): Cardinal;
berechnet zur Zahl deren Index als Primzahl. Falls Value selber keine Primzahl ist wird auf die vorhergehende oder nachfolgende Primzahl der Index berechnet (abhängig vom Parameter LowerBound).

.Count(LowerBound, UpperBound: Cardinal): Cardinal;
berechnet die Anzahl von Primzahlen die sich zwischen LowerBound und UpperBound befinden aus. Diese Methode berechnet intern nicht die realen Primzahlen was sie sogar noch schneller macht.

.BuildCache(const FileName: String; Bound: Cardinal);
erzeugt einen Lookup Tabelle in einer Datei die alle Primzahlen bis Bound enthält. Wird Bound auf MaxCardinal gesetzt (sprich alle Zahlen im maximalen Zahlenbereich des Siebes) so wird diese Datei ca. 630 Mb groß sein.

.LoadCache(const FileName);
Mit dieser Methode kann nun das Sieb so eingestellt werden das es eine Lookuptabelle benutzen kann. Damit werden random Zugriffe über .Count() / .Prime[] / IndexOf() usw. nochmals beschleunigt. Werden alerdings die Primzahlen/Berechnungen linear sequentiell benötigt dann lohnt ein Cache sich nicht. Die dynamische Berechnung der Primzahlen ist dann schneller als das Nachladen aus dem Cache.

Nun einige Beispiele:

Delphi-Quellcode:

  WriteLn( Primes.Count(10000000, 20000000) );  // Anzahl der Primzahlen zwischen 10-20 Mio berechnen
  
  I := Primes.IndexOf(10000000, False);                // Index der ersten Primzahl > 10 Mio berechnen
  J := Primes.IndexOf(20000000, True);                 // Index der letzten Primzahl < 20 Mio berechnen

  for I := I to J do                                  // Ausgabe der Primzahlen zwischen > 10Mio bis < 20Mio
    WriteLn( Primes[I] );

[KLS]

Also mein Primzahlenrechner braucht für den bereich 0-2.000.000.000 ganze 58,5s und ~121MB RAM.

Mein rechner hat 1GB ram und ist mit einem P4 (3GHz) ausgestattet.