# On complexity of the sieve, start crossing at the square of p - Part II

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

• 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?
– D.W.
Nov 21, 2016 at 2:03
• The question is why it is $O(n / \log n)$. Nov 21, 2016 at 2:21
• 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!
– D.W.
Nov 21, 2016 at 16:52

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)$.
• 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)$. Nov 21, 2016 at 12:50
• Besides that, the "original" unoptimized sieve is already $O(n log log n)$. So this little optimization cannot be worse than that. Nov 21, 2016 at 12:54
• 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}$. Nov 21, 2016 at 12:55
• Ok, what is exactly the problem if $n/p - p < 0$? Is a problem only for asintotics analysis? Nov 21, 2016 at 15:47
• 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. Nov 21, 2016 at 15:53