Sieve of Eratosthenes purpose of +1

let limit = [1,2,3,4,];
const output = new Array(limit + 1).fill(true);

Does anyone know the purpose of + 1?

https://www.codecademy.com/paths/back-end-engineer-career-path/tracks/becp-22-interview-skills/modules/wdcp-22-javascript-algorithm-practice/articles/sieve-of-eratosthenes-javascript

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 :smiley:

1 Like

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