Sieve di algoritmo di Eratostene in JavaScript che funziona senza fine per il grande numero

Question

Ho cercato di scrivere l'algoritmo Sieve of Eratosthenes in JavaScript. Fondamentalmente ho appena letteralmente seguito le istruzioni riportate di seguito:

1. creare un elenco di numeri interi consecutivi da 2 a (n-1)
2. Let primo numero primo p pari 2
3. A partire da p, conta in incrementi di p e rimuove ciascuno di questi numeri (p e multipli di p)
4. Vai al successivo numero della lista e ripetere 2,3,4
5. Aggiungi cancellato involontario numeri primi di nuovo alla lista

e questo è quello che ho messo a punto:

function eratosthenes(n){ 
var array = []; 
var tmpArray = []; // for containing unintentionally deleted elements like 2,3,5,7,... 
var maxPrimeFactor = 0; 
var upperLimit = Math.sqrt(n); 
var output = []; 

// Eratosthenes algorithm to find all primes under n 

// Make an array from 2 to (n - 1) 
//used as a base array to delete composite number from 
for(var i = 2; i < n; i++){ 
    array.push(i); 
} 

// Remove multiples of primes starting from 2, 3, 5,... 
for(var i = array[0]; i < upperLimit; i = array[0]){ 
    removeMultiples: 
    for(var j = i, k = i; j < n; j += i){ 
     var index = array.indexOf(j); 
     if(index === -1) 
      continue removeMultiples; 
     else 
      array.splice(index,1); 
    } 
    tmpArray.push(k); 
} 
array.unshift(tmpArray); 
return array; 
} 

Funziona per numeri piccoli, ma non per i numeri più grandi di un milione. Ho usato Node.js per testare e il processo sembra infinito e nessun errore di memoria mostrato. Ho letto una soluzione here (anche in javascript) ma non riesco ancora a comprenderla completamente.

Domanda: come fare questo lavoro per numeri sufficientemente grandi come un milione e oltre?

Answer 1

Si sta rendendo il Sieve di Eratostene intenzionalmente più lento utilizzando le funzioni di manipolazione degli array come Array#indexOf e Array#splice che viene eseguito in tempo lineare. Quando puoi avere O (1) per entrambe le operazioni coinvolte.

Di seguito il crivello di Eratostene seguendo tradizionali pratiche di programmazione:

var eratosthenes = function(n) { 
    // Eratosthenes algorithm to find all primes under n 
    var array = [], upperLimit = Math.sqrt(n), output = []; 

    // Make an array from 2 to (n - 1) 
    for (var i = 0; i < n; i++) { 
     array.push(true); 
    } 

    // Remove multiples of primes starting from 2, 3, 5,... 
    for (var i = 2; i <= upperLimit; i++) { 
     if (array[i]) { 
      for (var j = i * i; j < n; j += i) { 
       array[j] = false; 
      } 
     } 
    } 

    // All array[i] set to true are primes 
    for (var i = 2; i < n; i++) { 
     if(array[i]) { 
      output.push(i); 
     } 
    } 

    return output; 
}; 

You can see a live example for n = 1 000 000 here.

Answer 2

questa domanda è un po 'avaro sul lato basso nella definizione di ciò che è e accetta un "gran numero" che inizia a solo circa un milione, per cui il current answer funziona; tuttavia, utilizza un bel po 'di memoria come in un numero di 8 byte (un doppio reale di 64 bit) per ogni elemento da setacciare e un altro numero di 8 byte per ogni primo trovato. Questa risposta non funzionerebbe per "grandi numeri", ad esempio circa 250 milioni e oltre, in quanto supererebbe la quantità di memoria disponibile per la macchina di esecuzione JavaScript.

Il seguente codice JavaScript che implementa il Sieve a segmenti segmentato "infinito" (non limitato) di Eratostene supera questo problema in quanto utilizza solo un buffer di setacciamento di pagina 16 Kilobyte un bit ricco (un bit rappresenta un potenziale numero primo) e solo utilizza lo spazio di archiviazione per i numeri primi base fino alla radice quadrata del numero più alto corrente nel segmento di pagina corrente, con i numeri primi effettivamente trovati enumerati nell'ordine senza richiedere alcuna memorizzazione; anche risparmio di tempo da solo setacciando compositi dispari come l'unico primo pari è 2:

var SoEPgClass = (function() { 
    function SoEPgClass() { 
    this.bi = -1; // constructor resets the enumeration to start... 
    } 
    SoEPgClass.prototype.next = function() { 
    if (this.bi < 1) { 
     if (this.bi < 0) { 
     this.bi++; 
     this.lowi = 0; // other initialization done here... 
     this.bpa = []; 
     return 2; 
     } else { // bi must be zero: 
     var nxt = 3 + 2 * this.lowi + 262144; //just beyond the current page 
     this.buf = []; 
     for (var i = 0; i < 2048; i++) this.buf.push(0); // faster initialization 16 KByte's: 
     if (this.lowi <= 0) { // special culling for first page as no base primes yet: 
      for (var i = 0, p = 3, sqr = 9; sqr < nxt; i++, p += 2, sqr = p * p) 
      if ((this.buf[i >> 5] & (1 << (i & 31))) === 0) 
       for (var j = (sqr - 3) >> 1; j < 131072; j += p) 
       this.buf[j >> 5] |= 1 << (j & 31); 
     } else { // other than the first "zeroth" page: 
      if (!this.bpa.length) { // if this is the first page after the zero one: 
      this.bps = new SoEPgClass(); // initialize separate base primes stream: 
      this.bps.next(); // advance past the only even prime of 2 
      this.bpa.push(this.bps.next()); // keep the next prime (3 in this case) 
      } 
      // get enough base primes for the page range... 
      for (var p = this.bpa[this.bpa.length - 1], sqr = p * p; sqr < nxt; 
      p = this.bps.next(), this.bpa.push(p), sqr = p * p); 
      for (var i = 0; i < this.bpa.length; i++) { //for each base prime in the array 
      var p = this.bpa[i]; 
      var s = (p * p - 3) >> 1; //compute the start index of the prime squared 
      if (s >= this.lowi) // adjust start index based on page lower limit... 
       s -= this.lowi; 
      else { //for the case where this isn't the first prime squared instance 
       var r = (this.lowi - s) % p; 
       s = (r != 0) ? p - r : 0; 
      } 
      //inner tight composite culling loop for given prime number across page 
      for (var j = s; j < 131072; j += p) this.buf[j >> 5] |= 1 << (j & 31); 
      } 
     } 
     } 
    } 
    //find next marker still with prime status 
    while (this.bi < 131072 && this.buf[this.bi >> 5] & (1 << (this.bi & 31))) .bi++; 
    if (this.bi < 131072) // within buffer: output computed prime 
     return 3 + ((this.lowi + this.bi++) * 2); 
    else { // beyond buffer range: advance buffer 
     this.bi = 0; 
     this.lowi += 131072; 
     return this.next(); // and recursively loop just once to make a new page buffer 
    } 
    }; 
    return SoEPgClass; 
})(); 

Il codice di cui sopra può essere utilizzato per contare i numeri primi fino al limite dato dalla seguente codice JavaScript:

window.onload = function() { 
    var elpsd = -new Date().getTime(); 
    var top_num = 1000000000; 
    var cnt = 0; 
    var gen = new SoEPgClass(); 
    while (gen.next() <= top_num) cnt++; 
    elpsd += (new Date()).getTime(); 
    document.getElementById('content') 
    .innerText = 'Found ' + cnt + ' primes up to ' + top_num + ' in ' + elpsd + ' milliseconds.'; 
}; 

Se i suddetti due pezzi di codice JavaScript sono inseriti in un file denominato app.js nella stessa cartella del seguente codice HTML chiamato qualunque.html, si sarà in grado di eseguire il codice nel browser aprendo il file HTML in esso:

<!DOCTYPE html> 

<html lang="en"> 
    <head> 
    <meta charset="utf-8" /> 
    <title>Page Segmented Sieve of Eratosthenes in JavaScript</title> 
    <script src="app.js"></script> 
    </head> 
    <body> 
    <h1>Page Segmented Sieve of Eratosthenes in JavaScript.</h1> 

    <div id="content"></div> 
    </body> 
</html> 

Questo codice può setaccio a un miliardo di gamma è un paio di 10 di secondi quando viene eseguito su un motore di esecuzione JavaScript utilizzando la compilazione Just-In-Time (JIT) come il motore V8 di Google Chrome. Ulteriori guadagni possono essere ottenuti utilizzando la fattorizzazione di ruote estreme e il pre-culling dei buffer di pagina dei numeri primi più bassi, nel qual caso la quantità di lavoro eseguita può essere ridotta di un ulteriore fattore di quattro, il che significa che il numero di numeri primi può essere contato fino a un miliardo in pochi secondi (il conteggio non richiede l'enumerazione come qui usata, ma piuttosto può utilizzare il conteggio dei bit per cercare le tabelle sui buffer del segmento di pagina direttamente), sebbene a costo di una maggiore complessità del codice.

Answer 3

Solo per il gusto di farlo, ho implementato l'algoritmo Erastoten setaccia (eseguito con Node) seguendo rigorosamente le regole del TDD. Questa versione dovrebbe essere sufficiente per le interviste, come un esercizio scolastico o semplicemente come lo ero io - per scherzare un po '.

Lasciatemi dire che penso che la risposta accettata dovrebbe essere quella fornita da GordonBGood.

module.exports.compute = function(size) 
{ 
    if (!utils.isPositiveInteger(size)) 
    { 
     throw new TypeError("Input must be a positive integer"); 
    } 

    console.time('optimal'); 
    console.log(); 
    console.log("Starting for optimal computation where size = " + size); 
    let sieve = utils.generateArraySeq(2, size); 

    let prime = 2; 
    while (prime) 
    { 
     // mark multiples 
     for (let i = 0; i < sieve.length; i += prime) 
     { 
      if (sieve[i] !== prime) 
      { 
       sieve[i] = -1; 
      } 
     } 

     let old_prime = prime; 
     // find next prime number 
     for (let i = 0; i < sieve.length; i++) 
     { 
      if ((sieve[i] !== -1) && (sieve[i] > prime)) 
      { 
       prime = sieve[i]; 
       break; 
      } 
     } 

     if (old_prime === prime) 
     { 
      break; 
     } 
    } 
    console.timeEnd('optimal'); 
    // remove marked elements from the array 
    return sieve.filter( 
     function(element) 
     { 
      return element !== -1; 
     }); 
} // compute 

Apprezzerò qualsiasi critica significativa.

The whole repository can be found on my github account.

Answer 4

vorrei pubblicare questo come commento ad Alessandro, ma non hanno la reputazione di farlo. La sua risposta è fantastica, e questo è solo un ritocco per renderlo più veloce. Ho fatto un benchmark testando n = 100.000.000.

Invece di usare true e false in 'array', ottengo un grande aumento di velocità usando 1 e 0. Questo ha ridotto il mio tempo in Chrome da 5000 ms a 4250 ms. Firefox non è stato modificato (5600 ms in entrambi i casi).

Quindi possiamo prendere in considerazione che anche i numeri non saranno mai primi. Metti 2 in "uscita" dalla mazza e puoi fare i = 3; i + = 2, e j + = i * 2 durante il setaccio (possiamo saltare i multipli pari da quando un numero pari a un numero pari è pari), purché anche io + = 2 mentre si preme su "output" sul fine. Ciò ha ridotto il mio tempo in Chrome da 4250 ms a 3350 ms. Firefox ne ha beneficiato un po 'meno, passando da 5600 ms a 4800 ms.

In ogni caso, la combinazione di queste due modifiche mi ha dato un aumento della velocità del 33% in Chrome e un aumento del 14% in Firefox. Ecco la versione migliorata del codice di Alexander.

var eratosthenes = function(n) { 
    // Eratosthenes algorithm to find all primes under n 
    var array = [], upperLimit = Math.sqrt(n), output = [2]; 

    // Make an array from 2 to (n - 1) 
    for (var i = 0; i < n; i++) 
     array.push(1); 

    // Remove multiples of primes starting from 2, 3, 5,... 
    for (var i = 3; i <= upperLimit; i += 2) { 
     if (array[i]) { 
      for (var j = i * i; j < n; j += i*2) 
       array[j] = 0; 
     } 
    } 

    // All array[i] set to 1 (true) are primes 
    for (var i = 3; i < n; i += 2) { 
     if(array[i]) { 
      output.push(i); 
     } 
    } 

    return output; 
};