# 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;
for (int a = 2; a <= SQRT; a++)
if (!not_prime[a])
for (int c = MAX / a, b = a * c; c >= 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 >= b; b = a * c. But I forgot why I set restriction on c that c >= a? Could anyone help explain this line for me and help me analyze how efficient this algorithm is?

• I forgot why I … don't write, never present undocumented/uncommented code… (Not to add to post above as already on the verge between off- & on-topic: what comment did you leave out above?) Dec 13 '20 at 12:40
• (When c has fallen below a, b would be less than a² and have one divisor less than a unless prime. Pretty much standard Eratosthenes?!) Dec 13 '20 at 12:56
• LoL, I just found that !not_prime[a] means a is prime while I said in my post it was a composite... I think your comment is correct btw. @greybeard Dec 13 '20 at 13:33
• (Negative names are rarely best choice - consider is_composite. Or try and draw upon Code Review@SE.) Dec 13 '20 at 13:39
• That’s a weird looking inner loop you’ve got there, and I don’t understand the reason for even having the if condition inside it. You know that b is a multiple of something, so just mark it unconditionally as a composite. As for time complexity, say you’re sieving up to maximum $N$. It takes $O(N)$ time to prepare the sieve and read it back. Marking off multiples of 2 takes $N/2$ time, multiples of 3 take $N/3$ time, and so all up you get $N + N/2 + N/3 + \cdots + N/\sqrt{N} = O(N \log N)$ (by a property of harmonic numbers). A slightly tighter analysis can get $O(N \log \log N)$. Dec 14 '20 at 11:49