Sehr schneller Primzahl-Finder

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