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.

[Nicodius]

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

[Luckie]

Zitat von Luckie:

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

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 von MagicAndre1981:

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

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

......

[sakura]

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

......

[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 von negaH:

in 13 Sekunden auf einem P4 1,5MHz

Das is ne Leistung

[gordon freeman]

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.