Programmierung zum Wochenstart

[Rolf B]

Hallo,

hier ist meine Lösung, 1:1 kopiert aus der Nachricht an 1UP. Sie verwendet BigInt, und ist vermutlich deshalb schneller, weil meine Klasse SieveFactor es vermeidet, bei der sieve(c)-Prüfung zu dividieren. Eine BigInt Division dürfte relativ langsam sein. Deswegen addiere ich hoch - also genau das, was man in Erastosthenes so macht. Die Kunst war, die Siebschleife jedes Primfaktors unterbrechbar zu machen und nur bei Bedarf so weit wie nötig laufen zu lassen.

Die Geschwindigkeit lässt sich übrigens beinahe verdoppeln (bei mir von 3500ms auf 2000ms für die Primzahlen bis 1000.000), wenn man Speicher investiert und dem SieveFactor ein Property fsquare gönnt, in dem das Quadrat des Faktors steht. Dann muss man in isAbort nicht jedesmal neu quadrieren. Ich habe das mal auskommentiert hinzugefügt. Das Doppelte des Faktors zu speichern um eine Addition in der while-Schleife zu sparen hat sich nicht gelohnt.

Speicher für unnötige BigInt Objekte (weil die meisten SieveFactor Objekte nicht zum Sieben gebraucht werden) könnte man noch sparen, indem man this.value und this.fsquare erst in der sieve-Methode erzeugt, wenn diese das erste Mal verwendet wird. Die Abfrage auf Initialisiertheit bremst sieve aber etwas ab - es sei denn, man hext sich was mit Funktionsreferenzen zurecht. Habe ich getestet, aber bei den Zahlen bis 1000.000 ist der Speicher kaum relevant und die Laufzeit unterscheidet sich so wenig, dass es in den Mess-Schwankungen untergeht. Die Hexerei SCHEINT ein paar ms zu bringen, aber bei Messwerten von 1900ms bis 2050ms ist das nicht signifikant genug.

Akrobatische Kunststücke auf Trampolins waren mir nicht geheuer, das hab ich seingelassen.

let getPrimes = (function() {
   // SieveFactor repräsentiert eine Primzahl und ihre (2n+1)-fachen für den
   // Erastothenes-Algorithmus und stellt eine Eliminier-Schleife für einen
   // Primfaktor im Siebalgorithmus dar, die gerade so weit läuft wie für einen
   // Kandidaten nötig ist und dann Pause macht.
   // Die (2n)-fachen des Primfaktors interessieren nicht, das sind
   // gerade Zahlen und werden vom Generator gar nicht erst angefragt.
   class SieveFactor {
      // Speichere das 2n+1-fache als value-Property
      // Hat diverse Vorteile: es ist fixer und man muss nicht wissen, ob n ein BigInt ist 
      // oder nicht. 
      constructor(n) {
         this.factor = n;
         this.value = n;
//  ->   this.fsquare = n*n;
      }
      // Endebedingung: eine bekannte Primzahl ist größer als sqrt(Kandidat)
      isAbort(c) {
         return c < this.factor*this.factor;   /* c < this->fsquare */
      }
      // Versuche den Kandidaten auszusieben. Die Methode liefert true, wenn
      // die Abbruchbedingung erreicht ist, oder wenn der Kandidat ein (2n+1)-faches des
      // Faktors ist.
      sieve(c) {
         if (this.isAbort(c)) 
            return true;
         // Ist der Value kleiner als der Kandidat, ist die Erastothenes-Schleife für 
         // diesen Primfaktor noch nicht weit genug gelaufen. Diese Durchläufe jetzt
         // durchführen. 
         while (this.value < c)
             this.value += this.factor + this.factor;
         // Ok, jetzt kann geprüft werden ob der Kandidat ein Vielfaches des Faktors ist.
         return this.value == c;
      }
   }

   // Generatorfunktion für Primzahlen. 
   return function* () {
      // 2 ist eine. 
      yield BigInt(2);
   
      // Gefundene Siebfaktoren
      let factors = [];

      // Ab geht's, Endlosschleife ab 3 in 2-er Schritten 
      for (let candidate = BigInt(3); true; candidate += BigInt(2)) {
         // Versuche den Kandidaten auszusieben
         let factor = factors.find(s => s.sieve(candidate));
         // Kein Sandkorn oder eins mit Abbruch-Bedingung -> Kandidat ist prim
         if (!factor || factor.isAbort(candidate)) {
            yield candidate;
            factors.push(new SieveFactor(candidate));
         }
      }
   };
})();

// Test, liefert bei mir 78499 Primzahlen in 2 Sekunden.
console.clear();
console.log("begin");
let num = 0;
let start = Date.now();
for (let p of getPrimes()) {
   //console.log(p);
   num++;
   if (p > 1000000) break;
}
console.log("found " + num + " primes in " + (Date.now()-start) + "ms");

Rolf