Implementing the Page Segmented Sieve of Eratosthenes in Javascript

by

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]

129 thoughts on “Implementing the Page Segmented Sieve of Eratosthenes in Javascript”

Leave a Comment