Prime Sieve Logic

Prime sieve “solution”:

How does this bit make sense

1) Why do we need the if check, if the number will be guaranteed to be in the array?
2) Why mark prime → prime**2 as “not prime”? Isn’t this just lazy? This will have unnecessary repitition.


The if condition doesn’t check if the number i is in the range. The if condition checks if isPrime[i] == true

I don’t know what you mean by ‘lazy’. That loop marks every multiple of i as ‘not prime’ since i is prime. This happens exactly as many times as it needs to.

The prime sieve can be a tricky solution to understand.

1 Like

I’m stupid and read j+=i as j++

I just realised I used the exact same method, but mutated the array instead of marking and filtering