Akshay Khetrapal Akshay Khetrapal - 3 months ago 12
Javascript Question

Implementing Segmented Sieve of Eratosthenes in Javascript

I recently read about a faster implementation of Segmented Sieve of Eratosthenes for really big numbers.

Following is an implementation of the same:

function sieve(low, high) {

var primeArray = [], ll = Math.sqrt(low), output = [];

for (var i = 0; i < high; i++) {
primeArray[i] = true;
}

for (var i = 2; i <= ll; i++) {
if (primeArray[i]) {
for (var j = i * i; j < high; j += i) {
primeArray[j] = false;
}
}
}

for (var i = 2; i < ll; i++) {
if(primeArray[i])
{
var segmentStart = Math.floor(low/i) * i;

for(var j = segmentStart; j <= high; j+=i)
{
primeArray[j] = false;
}
}
}

for(var i = low; i <= high; i++)
{
if(primeArray[i])
{
output.push(i);
}
}

return output;
};


I cannot seem to figure out where have I got it wrong.
Probably been working at it too long.

For example:

sieve(4,10)
should return
[5,7]

But it is returning
[5,7,9]

Answer

You are not checking for high enough factors. The reason is that your square root limit is wrong. Change:

ll = Math.sqrt(low)

to

ll = Math.sqrt(high)

The first loop should also loop to high inclusive, since the output loop at the end does the same. For the same reason the third outer loop should also loop to ll inclusive.

The part that calculates the starting point for the segment should be sure not to wipe out a prime in its first iteration. This typically happens when low is low, like 1. So add this:

            if (primeArray[segmentStart]) segmentStart += i; 

Note that you can use ceil instead of floor in the segmentation part.

The corrected code would look like this:

function sieve(low, high) {
    var primeArray = [], ll = Math.sqrt(high), output = [];

    for (var i = 2; i <= high; i++) {
        primeArray[i] = true;
    }

    for (var i = 2; i <= ll; i++) {
        if (primeArray[i]) {
            for (var j = i * i; j <= high; j += i) {
                primeArray[j] = false;
            }
        }
    }

    for (var i = 2; i <= ll; i++) {
        if(primeArray[i]) {
            var segmentStart = Math.ceil(low/i) * i;
            // need this test to ensure we are not deleting primes
            if (primeArray[segmentStart]) segmentStart += i; 

            for(var j = segmentStart; j <= high; j+=i) {
                primeArray[j] = false;
            }
        }
    }

    for(var i = low; i <= high; i++) {
        if(primeArray[i]) {
            output.push(i);
        }
    }
    return output;
}

console.log(sieve(1, 20));