4
$\begingroup$

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?

$\endgroup$
  • $\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 '16 at 11:32
5
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ But it is not just that, also i need a step of p..., or there is no optimization. $\endgroup$ – Wyvern666 Nov 17 '16 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$ – Yuval Filmus Nov 17 '16 at 21:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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