# On complexity of the sieve, start crossing at the square of $p$

This question is about a common optimization in the basic sieve of Erathostenes.

If we look at this paper (page 3, footnotes), the author says:

If we start crossing off at $p^2$ rather than $p$, the number of composites we cross off is $\frac{n}{p}−p+1$, but it makes no significant difference to our sum, because it only subtracts an irrelevant $O(n/ \log n)$ factor

Similarly, I have seen the same conclusion in other places, so according to them we have that the total cost counting crossings is about (ignoring the $\sqrt n$ optimization):

$\sum_{p\leq n}(\frac{n}{p}-p+1)$

Where $p$ is prime.

But if we look at this algorithm (in pseudocode) implementing this same optimization:

//omitting sieve[2..n] initialization
for p:=2 to n
if (sieve[p] is prime)
for k:=p^2 to floor(n/p)
sieve[k*p] := not prime     //cross multiples of p


I would say the total cost is:

$\sum_{p\leq n}(\frac{n}{p}-p^2+1)$

because the cost of the inner loop is

$\sum_{k=p^2}^{\frac{n}{p}}=\frac{n}{p}-p^2+1$

Am I wrong?

• As others found, the first item you remove is p^3, which is wrong. Much better savings can be made not putting even numbers into the sieve at all, considering that all even numbers except 2 or non-prime. And in practice, huge savings will be made by using a cache friendly algorithm. – gnasher729 Nov 18 '16 at 11:32

Your algorithm is wrong. The starting point should be $p$ rather than $p^2$, since in the body of the loop $k$ gets multiplied by $p$.
• Starting to cross off at $p^2$ is the same as starting at $k = p$. Otherwise you might have started at $k = 2$. – Yuval Filmus Nov 17 '16 at 21:38