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 >= a? Could anyone help explain this line for me and help me analyze how efficient this algorithm is?