How efficient of this prime sieving algorithm? I just found there is an old program of mine where I implemented the following prime sieving algorithm:
#define MAX=1000001
#define SQRT=1000
// ...
not_prime[1] = 1;
for (int a = 2; a &lt;= SQRT; a++)
  if (!not_prime[a])
     for (int c = MAX / a, b = a * c; c &gt;= a; c--, b -= a)
        if (!not_prime[c])
           not_prime[b] = 1;

It seems like my logic that time is: For any given composite a and all corresponding composite cs such that MAX &gt;= b; b = a * c. But I forgot why I set restriction on c that c &gt;= a? Could anyone help explain this line for me and help me analyze how efficient this algorithm is?
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.