arrays - Sieve of Eratosthenes algorithm in JavaScript running endless for large number

Question

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?

Answer 1

You are making the Sieve of Eratosthenes much 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.