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 <= 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 c
s 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?) $\endgroup$ – greybeard Dec 13 '20 at 12:40c
has fallen belowa
,b
would be less thana
² and have one divisor less thana
unless prime. Pretty much standard Eratosthenes?!) $\endgroup$ – greybeard Dec 13 '20 at 12:56!not_prime[a]
meansa
is prime while I said in my post it was a composite... I think your comment is correct btw. @greybeard $\endgroup$ – Kindred Dec 13 '20 at 13:33is_composite
. Or try and draw upon Code Review@SE.) $\endgroup$ – greybeard Dec 13 '20 at 13:39b
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)$. $\endgroup$ – Joppy Dec 14 '20 at 11:49