Comment by jventura | Hacker News Reader

Comment by jventura | Hacker News Reader

Parent Full thread

There's a small optimization on the original article which I think your implementation doesn't do: "At each stage we know that every composite number up to p^2 has definitely been marked as such"..

Assuming your implementation is working fine (didn't test it), I think the change would be j = i * i on the inline for:

  void sieve()
  {
      for(int i = 2; i < n; i++)
          for (int j = i*i; j < n; j += i) p[j]++;
  }

It's tricky to explain, but take for instance the numbers from 1 to 20. When i=2, it will clear [4, 6, 8, 10, 12, 14, 16, 18, 20] as non-primes. So when i=3, you can skip 6 (which was cleared by i=2) and start directly at 9 (i * i = 3 * 3) to clear [9, 12, 15, 18]. Also, when i=4, you can skip the 8 and 12 (which were cleared by i=2 and i=3) and start on 16 to clear [16, 20]. Finally, when i=5, you can start directly at 25 (out of bounds in this case) because 10, 15 and 20 were already cleared by the previous iterations..

Edit: But as other posters are saying below, the original sieves algorithm shouldn't even have to test i=4 because the numbers it clears (naivelly [4,8,12,16,20]) have already been cleared by the previous iterations of the algorithm.

> It's tricky to explain

This reasoning is fairly simple:

Suppose we have a composite number K that is less than P^2.

Then K = A * B, for some A and B not equal to 1, (which is the definition of composite). Let us say that A is less than or equal to B. (If this is not the case, switch the labels.)

Then A must be less than P:

If A is greater than P, K = A * B > A * P > P^2. But we chose K such that K < P^2.

If A is less than P, then K will have been marked during the cycle of Q, a prime divisor of A, which will occur before P. Therefore, we do not need to examine any numbers below P^2 -- they are either prime or have been marked.

Maybe stop the outer loop as soon as i * i > n then as well.

Also, where's the check whether `i` is actually prime before you start crossing off multiples? You don't need to cross off multiples of composite numbers.

> Also, where's the check whether `i` is actually prime before you start crossing of multiples? You don't need to cross off multiples of composite numbers.

You are absolutely right as the original method seems to specify that. I've edited my answer to show it.

So the function would be something like (untested):

  void sieve()
  {
      for (int i = 2; i*i < n; i++)
          if (p[i] == 1)
              for (int j = i*i; j < n; j += i) p[j]++;
  }

There's the problem, as other posters are saying, that if p[j] == 1 is because it was cleared as non-prime, but I've just tested p[i] == 1 for primality for coherence with the original author.

You can avoid the more expensive squaring in favour of addition if you keep a couple of extra counters.

Reply on news.ycombinator.com