In words, the process you’re doing says “zero out the flags for all multiples of this number.” The if statement says “do the next step only if the current number is a prime.”
The second sieve has to zero out all multiples of 2, then 3, then 4, … for every number in the sieve. The first one zeroes out only multiples of primes: 2, then 3, then …
When it reaches 4, it sees that 4 is already zeroed. Any multiple of 4 is also a multiple of 2, so they’re already zeroed. Marking them again is wasted work.
Now we do 5, skip 6, do 7, skip 8, 9, and 10, …
When we do that work only for prime divisors, we save a lot of work.
4
solved Why ‘IF’ made this code 2x faster as the output is the same and ‘IF’ make an extra check? [closed]