Akshay Khetrapal - 1 year ago 104
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]`

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

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download