> 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

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