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
    It is not well known to me. Could you direct me to some reference?2011-06-20
  • 0
    @yayu: Apostol's book, Introduction to Analytic Number theory, theorem 4.12.2011-06-20
  • 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
    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)2011-06-20
  • 0
    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.2011-06-20
  • 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