Estimating number of crossings for Erastothenes' Sieve

Question

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.

Answer 1

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

And so your sum is

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

Answer 2

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