0
$\begingroup$

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 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?

Improve this question
$\endgroup$
5
  • $\begingroup$ 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:40
  • $\begingroup$ (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?!) $\endgroup$ – greybeard Dec 13 '20 at 12:56
  • $\begingroup$ 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 $\endgroup$ – Kindred Dec 13 '20 at 13:33
  • 1
    $\begingroup$ (Negative names are rarely best choice - consider is_composite. Or try and draw upon Code Review@SE.) $\endgroup$ – greybeard Dec 13 '20 at 13:39
  • $\begingroup$ 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)$. $\endgroup$ – Joppy Dec 14 '20 at 11:49
1
$\begingroup$

The loop "int c ... " 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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.