Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
See also: stackoverflow.com/questions/2582732/… –  Aryabhata Jun 20 '11 at 6:40

2 Answers 2

up vote 2 down vote accepted

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$

share|improve this answer
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
Dear @Chandru. Please look at my accept rate, I do not let answers go unaccepted. If I haven't accepted an answer it means I am still thinking about it, which it seems will be the case with this one. Tomorrow morning I'll be in the library with said book to convince myself this is so –  kuch nahi Jun 20 '11 at 6:43
@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)

share|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.