How efficient of this prime sieving algorithm?
The loop &quot;int c ... &quot; is much too complicated and difficult to get right, just start with c = a, b = a*a, and iterate upwards.
Most people create a sieve for odd numbers only. Some create a sieve only for the eight out of 30 numbers that are not multiples of 2, 3 or 5. That's a factor of 3.75 in space. And removing multiples of 2, 3 and 5 takes substantial time.
Only checking multiples of 2, 3 or 5 also allows you to check fewer multiples of the prime. Another factor 3.75.
If you want to be fast, you use a bit array, and use SIMD instructions to remove multiples of small primes, say up to 100, which saves a huge amount of time. Checking whether c is still considered a prime is time consuming and likely takes more time than it saves, especially since you will end up with lots of mispredicted branches.
Now for primes up to a million that's all irrelevant, but for larger ranges it makes a huge difference.