let limit = [1,2,3,4,];

const output = new Array(limit + 1).fill(true);

Does anyone know the purpose of + 1?

let limit = [1,2,3,4,];

const output = new Array(limit + 1).fill(true);

Does anyone know the purpose of + 1?

Limit should be an upper bound, not an array. The array is one more than the limit in length so that it will have a physical element at index ‘limit’.

Witness,

```
> limit = 20
<- 20
> new Array(limit + 1).fill(true)
<- (21) [true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]
```

Now allowing that the first index is zero, count the remaining elements. The last element will be index 20.

1 Like

Thank you. It is great to have someone answer our questions when we get stuck!

1 Like

Could you explain why it is j = j + i in the inner loop, instead of j++?

Sorry, I feel like I should know this…

```
for (let i = 2; i < Math.pow(limit, 0.5); i++) {
if (output[i] === true) {
// Mark all multiples of i as non-prime
for (let j = Math.pow(i, 2); j <= limit; j = j + i) {
output[j] = false;
}
}
}
```

Hi,

j is looping through all the multiples of i.

So, for example, if i was 3, j would start off at 9 ( 3 squared ), and then each loop would add another 3 ( i ) until you get to the limit and you’ve accounted for all multiples of 3;

So, 9, 12, 15, 18, …

1 Like

One thinks it would be simpler to start at `i * 2`

, given there is a test for ‘true’.

~~3~~, 6, 9, 12, 15, …

TBH, squaring the base number may reach all the non-primes. Don’t know for sure that there are any edge cases. Would need to be proven for the first N primes where N is very large. Out of my wheelhouse.

Hi,

It’s discussed on ops link as an optimization : First multiple.

Say, you’re at 5,

then you’ve already covered

2 * 5 when doing the 2s,

3 * 5 when doing the 3s,

4 * 5 when doing the 4s

So, you’re going to be covered for all the numbers up to the current number squared.

1 Like

Yeah, it just occurred to me. Good point.

for (let j = i * 2; j <= limit; j = j + i)

if i = 2 then…

for (let j = 4; j <= limit; j = 4+2) until limit reached.

Thank you for your help. I understand now

1 Like

This topic was automatically closed 41 days after the last reply. New replies are no longer allowed.