# Estimating number of crossings for Erastothenes' Sieve

In this paper (2.1) I need to understand the formula for the total number of operations: $$\sum_{i=1}^{\pi(\sqrt n)}\frac{n}{p_i} \approx n\ln \ln n + O(n)$$ On a sidenote, since we're only checking up till the square root then why shouldn't the summand be $\frac{\sqrt{n}}{p_i}$

I have taken sequences and series and calculus in the past but I am clueless regarding these sums one pages 3 and 4.

-
–  Aryabhata Jun 20 '11 at 6:40

It is well known that

$$\sum_{p \le x} \frac{1}{p} = \log \log x + A + \mathcal{O}(1/\log x)$$

And the prime number theorem states that $\pi(n) \sim \frac{n}{\log n}$

Thus your $x$ is $\sim \frac{2\sqrt{n}}{\log n}$

$$n\log \log \frac{2 \sqrt{n}}{\log n} + \mathcal{O}(n)$$

which is asymptotically

$$n \log \log n + \mathcal{O}(n)$$

as $\log \frac{\log n}{3} \le \log \log 2 \sqrt{n} \le \log \log n$

-
It is not well known to me. Could you direct me to some reference? –  kuch nahi Jun 20 '11 at 6:30
@yayu: Apostol's book, Introduction to Analytic Number theory, theorem 4.12. –  Aryabhata Jun 20 '11 at 6:38
@yayu: Time to accept an answer. –  user9413 Jun 20 '11 at 6:40
@yayu: Oh, no problem. Just reminded you :) as there many users who come and go and don't care about accepting answers. –  user9413 Jun 20 '11 at 6:52

$n/p_{i}$ is the number of multiples of $p_{i}$ less than or equal to n (I assume the floor isn't included for simplicity) that gives us the number of crossing performed. The sum is then performed over the number of primes under $\sqrt{n}$ (which the factors will not exceed)

-
I get that. The trouble I am addressing to is why use $\frac{n}{p}$ when we only cross off $\sqrt{n}$ (the floor function isnt included maybe because they are only looking at asymptotic behaviour) –  kuch nahi Jun 20 '11 at 6:32
Consider your list to be {1, 2, 3, ... , 10} (starting at 2 of course) the program will take 2 as the first prime and cross out all the multiples of 2 up until 10, not up until $\sqrt{10}$ which would only sieve primes up to 3; your list would only give 2 and 3 as primes instead of 2,3,5,7. –  Alfredo Z. Jun 20 '11 at 6:42
But if I am checking for the primality of $10$ I do not need anything $> \sqrt{10}$, (i.e 2 would be enough) –  kuch nahi Jun 20 '11 at 6:45