4 ms·

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

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.

stabbles 9y ago
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.
- jventura 9y ago
  > 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.
  - deleted 9y ago
    [deleted]
SomeStupidPoint 9y ago
> 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.
meta_AU 9y ago
You can avoid the more expensive squaring in favour of addition if you keep a couple of extra counters.

stabbles 9y ago

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.

jventura 9y ago
> 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.
- deleted 9y ago
  [deleted]

SomeStupidPoint 9y ago

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

meta_AU 9y ago

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