3 ms·
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
by 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]