2
$\begingroup$

Ok, this is a follow up question to this, about the Erathostenes Sieve.

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

The total cost counting crossings is:

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

The first sum would give us the known $O(n\log\log n)$. But I don't see the second sum to be an "irrelevant $O(n/\log n)$", so how is that?

According to this post in math overflow an upper bound for the sum of the primes up to $n$ is: $$\frac{n^2}{2\log n} + O\left(\frac{n^2}{\log^2 n}\right).$$

$\endgroup$
3
  • $\begingroup$ What is your question? Is your question why it is $O(n / \log n)$, or is your question why $O(n / \log n)$ is irrelevant in this context? $\endgroup$
    – D.W.
    Nov 21, 2016 at 2:03
  • $\begingroup$ The question is why it is $O(n / \log n)$. $\endgroup$
    – Wyvern666
    Nov 21, 2016 at 2:21
  • $\begingroup$ OK. Please edit the question to clarify that. We want questions to be self-contained: people shouldn't have to read the comments to understand what you are asking. (Comments exist primarily to help you improve your post, and can disappear at any time.) Thank you! $\endgroup$
    – D.W.
    Nov 21, 2016 at 16:52

1 Answer 1

3
$\begingroup$

The sum only goes up to $\sqrt{n}$. You can see that in the big display at the bottom of page 3, where only the first $\pi(\sqrt{n})$ primes are considered. Substituting $\sqrt{n}$ for $n$ in your formula, we get $n/\log n + O(n/\log^2 n)$.

$\endgroup$
5
  • $\begingroup$ Ok, i want to leave aside the $\sqrt n$ optimization and consider the square root only. Suppose we go up to $n$, then the second sum it is something like $O(n^2)$ right?, but that doesnt make sense because according every source i checked these optimizations doesnt affect the asintotic running time of the sieve, so anyway it must be $O(n log log n)$, in fact $\Theta(n log log n)$. $\endgroup$
    – Wyvern666
    Nov 21, 2016 at 12:50
  • $\begingroup$ Besides that, the "original" unoptimized sieve is already $O(n log log n)$. So this little optimization cannot be worse than that. $\endgroup$
    – Wyvern666
    Nov 21, 2016 at 12:54
  • 2
    $\begingroup$ When $p > \sqrt{n}$ you can't take $n/p - p + 1$, since $n/p - p < 0$! You should take $\max(n/p - p + 1,0)$, since when $p > \sqrt{n}$, the outcome of this optimization is that you do nothing for $p > \sqrt{n}$. $\endgroup$ Nov 21, 2016 at 12:55
  • $\begingroup$ Ok, what is exactly the problem if $n/p - p < 0$? Is a problem only for asintotics analysis? $\endgroup$
    – Wyvern666
    Nov 21, 2016 at 15:47
  • 2
    $\begingroup$ If $n/p - p < 0$ then you did something wrong. The loop cannot run a negative number of times. You should never forget that this is not just a formula, it also has some semantical meaning. $\endgroup$ Nov 21, 2016 at 15:53

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.