Akshay Khetrapal - 1 month ago 5x

Javascript Question

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

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

Source (Stackoverflow)

Comments