Sieve of Eratosthenes in JavaScript

Question

I found this method kinda tough to get for a beginner like me, but I tried to do my best, and here's what I came up with.

Is this good code regarding performance? Is there anything wrong with it?

var notPrime = [] ;
var prime = [] ;

var n = prompt("Enter n: ");

for(var i = 2 ; i < n ; i++ ){

    if(notPrime.indexOf(i) != -1){              
        continue;
    }   

    for(var j = i ; i <= j ; j++){
        if((i * j) < n){
            notPrime.push(i*j);
        } else {
            break;
        }
    }
    prime.push(i);
}

for(var f in prime){
    console.log(prime[f]);
}

Answer 1

Lets say that there is room for improvement. ;)

---

The prompt method returns a string, but you want a number, so you should parse the string:

var n = parseInt(prompt("Enter n: "), 10);

---

Using indexOf on an array is slow. Instead of putting all the non-primes in a bucket and rummaging through it, you should use an array containing boolean values where the index is the number and the values tells you if it's a prime or not.

Accessing an array by index is an O(1) operation, while searching for a value in an array is an O(n) operaton. As n grows, this code will get slower and slower the longer you let it run.

As you are pushing a lot of duplicate non-primes in the array, an array of boolean values will actually use about 70% less memory eventhough the primes also takes up space in it.

---

This loop is pretty pointless:

for(var j = i ; i <= j ; j++){

The condition will never be false. You should instead use the i * j < n condition to break out of the loop:

for(var j = i; i * j < n; j++){
  notPrime[i * j] = true;
}

---

Edit:

You are still using the array as a kind of collection. You should set all values to true at start, and then set all non-primes to false. This code (based on the algorithm here) is about five times faster:

var n = parseInt(prompt("Enter n: "), 10);
var i, j;
var prime = new Array(n);
for (i = 2; i < n ; i++) prime[i] = true;

for (i = 2; i * i < n ; i++) {
  if (prime[i]) {
    for (j = 0; i * i + i * j < n ; j++) {
      prime[i * i + i * j] = false;
    }
  }
}

var cnt = 0;
for (i = 2 ; i < n ; i++) {
  if (prime[i]){
    console.log(i);
  }
}

Answer 2

I made some improvements and speed up this code.

---

var prime = new Array(n);
for (i = 2; i < n ; i++) prime[i] = true;

replaced by 2x faster

var prime = [];
for (i = 0; i <= n ; i++) prime.push(true);

---

for (i = 2; i * i < n ; i++) {

i * i is calculated every time, replaced by

for (var i = 2; i <= Math.sqrt(n)|0; i++) {

Math.sqrt(n)|0 reduces unneeded calculations

---

for (j = 0; i * i + i * j <= n ; j++) {
  prime[i * i + i * j] = false;

Here are so many calculations iterated every time. I reduced them to:

for (var j = i*i; j <= n; j += i) {
  prime[j] = false;

---

function sieve5(n) {
  var i,j;
  // true-table
  var prime = [];
  for (i = 0; i <= n; i++) prime.push(true); // mark 'numbers' 0..n as 'true'

  // mark for swipe
  for (i = 2; i <= Math.sqrt(n)|0; i++) {
    if (prime[i]) {
      for (j = i*i; j <= n ;j += i) {
        prime[j] = false; // eliminate all none prime numbers and mark them as 'false'
      }
    }
  }

  // extract primes
  var primes = [];
  for (i = 2; i <= n; i++) { // 'zero' and 'one' is not prime
    if (prime[i]) primes.push(i) // get all primes from 2..n
  }

  return primes;
}
console.time("sieve5");
primes = sieve5(1000000);// 62ms on my PC
console.timeEnd("sieve5");
console.log('length=',primes.length);

primes = sieve5(100);
console.log(primes);
// [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
console.log(sieve5(11));//[2,3,5,7,11]