2
\$\begingroup\$

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;

}

\$\endgroup\$

migrated from stackoverflow.com Feb 11 '15 at 14:39

This question came from our site for professional and enthusiast programmers.

  • 2
    \$\begingroup\$ That's not a Sieve of Erathosthenes implementation. \$\endgroup\$ – Pointy Feb 11 '15 at 14:43
  • \$\begingroup\$ Here's a jsperf to compare. \$\endgroup\$ – Matt Burland Feb 11 '15 at 14:45
  • 2
    \$\begingroup\$ Calling splice deep inside nested loops... ouch \$\endgroup\$ – Esailija Feb 11 '15 at 14:45
  • \$\begingroup\$ @Pointy why isn't it? It's slightly modified, e.g. I don't bother pushing even numbers into the Array, but the essence of it is the same. \$\endgroup\$ – JamieC Feb 11 '15 at 14:55
  • \$\begingroup\$ See Sieve of Eratosthenes \$\endgroup\$ – Matt Burland Feb 11 '15 at 14:55
5
\$\begingroup\$

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;
}
\$\endgroup\$
2
\$\begingroup\$

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});
  }
\$\endgroup\$
  • 1
    \$\begingroup\$ This isn't a Sieve of Erathosthenes either. \$\endgroup\$ – Pointy Feb 11 '15 at 14:53
  • \$\begingroup\$ @Pointy how so? except that I use an int array where numbers[i]==i if prime instead of a boolean \$\endgroup\$ – ratchet freak Feb 11 '15 at 14:55
  • \$\begingroup\$ You don't want to keep track of the multiples of every number, just the primes. \$\endgroup\$ – Pointy Feb 11 '15 at 14:56
  • \$\begingroup\$ @Pointy there that's better ain't it \$\endgroup\$ – ratchet freak Feb 11 '15 at 14:58
  • \$\begingroup\$ I'm not sure why you initialize the sieve that way; none of the entries (other than numbers[0]) will ever be 0 in the actual loop. \$\endgroup\$ – Pointy Feb 11 '15 at 15:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.