Sieve of Eratosthenes JavaScript implementation - performance very slow over a certain number

Question

I've been playing around with the code challenges on projecteuler.net. A few of them involve prime numbers, so I've created a function to find them based on the sieve of Eratosthenes.

It works fine, and is reasonably quick for small numbers, but much slower for the challenges that involve the larger numbers, like 2million. So to try to improve my function I tested it to see how the performance changes and discovered that the time it takes to run shoots up dramatically at a specific number, not gradually as you might expect.

I'm running this on the chrome dev tools. It consistently takes about 1.5 seconds for 354,957 and 15 seconds for 354,958. I found this very odd and was wondering if anyone had experienced similar or new why this might be?

Below is my code. I know it's not perfect and there a much (much) quicker implementations out there.

function getPrimesUnder(number) {
  var start = new Date().getTime();

  var numbers = [2];
  var sqNum = Math.sqrt(number);
  var i, x;
  for (i = 3; i < number; i = i + 2) {
    numbers.push(i);
  }
  for (x = 0; numbers[x] < sqNum; x++) {
    for (i = 0; i < numbers.length ; i++){
       if (numbers[i] > numbers[x]) {
        if(numbers[i] % numbers[x] === 0){
          numbers.splice(i, 1)
        }
      }
    }
  }
  var end = new Date().getTime();
  var time = end - start;
  alert('Execution time: ' + time/1000 + ' seconds');
  return numbers;

}

Answer 1

In a real Sieve implementation, your "sieve" is the array that keeps track of the multiples of primes. You'll also want to remember the values of the primes, since the array is basically an array of Boolean values.

Thus, the first thing you do is create the array. It has to be as big as the biggest target value:

function primesBelow(n) {
  var sieve = new Array(n);

Upon initialization, that array is empty, and thankfully in JavaScript empty array elements look false. So we start with 2:

  var primes = [];
  for (var test = 2; test < n; ++test) {
    if (sieve[test]) {
      // NOT PRIME
    }
    else {

If the sieve value is unset at a particular test number, that means that that value is the multiple of no known prime. Hence, we can tick off that sieve entry (even though we'll never see it again) and all multiples of that newly-found prime:

      primes.push(test);
      for (var pm = test; pm < n; pm += test)
        sieve[pm] = true;
    }
  }

(Note that we really could start the value of pm at test * test, because the first composite number bigger than test for which test will be the only prime factor will be its square.)

When we start the loop at 2, the first prime we find is, clearly, 2 itself, since the sieve is freshly created and completely empty. So all the multiples of 2 will be set to true on the first pass. The second value to test is 3, and sieve[3] will still be false, because 3 is not a multiple of 2 and is therefore also prime.

The first composite number encountered will be 4, because its slot in the sieve will have been set to true when we found 2. Then 5 will be tested, and its sieve slot will also be empty, so it's prime too.

Note that the first odd composite number to be found is 9, which is not prime because its sieve slot will have been set to true when the loop found 3.

The complete code:

function primesBelow(n) {
  var sieve = new Array(n);
  var primes = [];
  for (var test = 2; test < n; ++test) {
    if (sieve[test]) {
      // NOT PRIME
    }
    else {
      primes.push(test);
      for (var pm = test; pm < n; pm += test)
        sieve[pm] = true;
    }
  }
  return primes;
}

Answer 2

numbers.splice is the culprit, this will take O(n) time each time it is called. And it is called O(n) times.

do a proper sieve instead:

for (i = 0; i < number; i++) {
    numbers.push(i);
}

 for (x = 2; numbers[x] < sqNum; x++) {
    if(numbers[x]==0)
        continue;

    for (i = x*2; i < numbers.length ; i+=x){
          numbers[i]=0;
      }
    }
  }

Otherwise use filter to remove all the multiples

  for (x = 0; numbers[x] < sqNum; x++) {
    if(numbers[x]==0)
        continue;

    numbers = numbers.filter(function(a){return a % numbers[x] != 0});
  }