2
$\begingroup$

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.

  • 0
    See also: http://stackoverflow.com/questions/2582732/time-complexity-of-sieve-of-eratosthenes-algorithm/2582776#25827762011-06-20

2 Answers 2

2

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$

  • 0
    @yayu: Oh, no problem. Just reminded you :) as there many users who come and go and don't care about accepting answers.2011-06-20
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)

  • 0
    But if I am checking for the primality of $10$ I do not need anything > \sqrt{10}, (i.e 2 would be enough)2011-06-20