Sieve of Eratosthenes in JavaScript

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

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

StackExchange Code Review Q#5334, answer score: 6