Sieve of Eratosthenes algorithm in JavaScript runn

问题:

I have been trying to write Sieve of Eratosthenes algorithm in JavaScript. Basically I just literally followed the steps below:

1. Create a list of consecutive integers from 2 to (n-1)
2. Let first prime number p equal 2
3. Starting from p, count up in increments of p and removes each of these numbers (p and multiples of p)
4. Go to the next number in the list and repeat 2,3,4
5. Add unintentionally deleted prime numbers back to the list

and this is what I have come up with:

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

It works for small numbers but not for numbers larger than one million. I used Node.js to test and the process just seems endless and no memory error shown up. I've read a solution here(also in javascript) but still cannot fully comprehend it.

Question: How to make this work for sufficiently large numbers such as one million and above?

回答1:

You are making the Sieve of Eratosthenes intentionally slower by making use of array manipulation functions such as Array#indexOf and Array#splice which runs in linear time. When you can have O(1) for both operations involved.

Below is the Sieve of Eratosthenes following conventional programming practices:

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.

回答2:

This question is a little stingy on the low side in the definition of what a "large number" is and accepts that it starts at only about a million, for which the current answer works; however, it uses quite a lot of memory as in one 8-byte number (a double real of 64 bits) for each element to be sieved and another 8-byte number for every found prime. That answer wouldn't work for "large numbers" of say about 250 million and above as it would exceed the amount of memory available to the JavaScript execution machine.

The following JavaScript code implementing the "infinite" (unbounded) Page Segmented Sieve of Eratosthenes overcomes that problem in that it only uses one bit-packed 16 Kilobyte page segmented sieving buffer (one bit represents one potential prime number) and only uses storage for the base primes up to the square root of the current highest number in the current page segment, with the actual found primes enumerated in order without requiring any storage; also saving time by only sieving odd composites as the only even prime is 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;
})();

The above code can be utilized to count the primes up to the given limit by the following JavaScript code:

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.';
};

If the above two pieces of JavaScript code are put into a file named app.js in the same folder as the following HTML code named whatever.html, you will be able to run the code in your browser by opening the HTML file in it:

<!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>

This code can sieve to the one billion range is a few 10's of seconds when run on a JavaScript execution engine using Just-In-Time (JIT) compilation such as Google Chrome's V8 engine. Further gains can be achieved by using extreme wheel factorization and pre-culling of the page buffers of the lowest base primes in which case the amount of work performed can be cut by a further factor of four, meaning that the number of primes can be counted up to a billion in a few seconds (counting does not require enumeration as used here but rather can use bit count look up tables on the page segment buffers directly), although at the cost of increased code complexity.

回答3:

I would post this as a comment to Alexander, but I don't have the reputation to do that. His answer is awesome, and this just tweaks it to make it faster. I benchmarked by testing n = 100,000,000.

Instead of using true and false in 'array', I get a big speed boost by using 1 and 0. This reduced my time in Chrome from 5000 ms to 4250 ms. Firefox was unaffected (5600 ms either way).

Then we can take into account that even numbers will never be prime. Put 2 into 'output' off the bat and you can do i=3; i += 2, and j += i*2 during the sieve (we can skip the even multiples since any number times an even number is even), as long as we also i += 2 while pushing to 'output' at the end. This reduced my time in Chrome from 4250 ms to 3350 ms. Firefox benefited a bit less, dropping from 5600 ms to 4800 ms.

Anyway, the combination of those two tweaks gave me a 33% speed boost in Chrome, and a 14% boost in Firefox. Here's the improved version of Alexander's code.

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

回答4:

Just for the fun of it, I implemented the Erastoten sieve algorithm (run with Node) strictly following the rules of TDD. This version should be enough for interviews, as a school exercise or just like I was - for messing around a bit.

Let me state, that I definitely think the accepted answer should be the one provided by 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

I will appreciate any senseful critique.

The whole repository can be found on my github account.