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


Am I wrong?

  • $\begingroup$ 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. $\endgroup$
    – gnasher729
    Nov 18, 2016 at 11:32

1 Answer 1


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

  • $\begingroup$ But it is not just that, also i need a step of p..., or there is no optimization. $\endgroup$
    – Wyvern666
    Nov 17, 2016 at 21:31
  • $\begingroup$ Starting to cross off at $p^2$ is the same as starting at $k = p$. Otherwise you might have started at $k = 2$. $\endgroup$ Nov 17, 2016 at 21:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.