Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I need to show that the number of primes up to $n$ (i.e. $\pi(n)$) is $O(n/\log n)$. In the previous exercise of this question I proved that ${\displaystyle \sum_{i=1}^{\pi(n)}\log p_{i}} \leq Cn$ for some constant $C$ (where $p_i$ is the i-th prime number) . I thought I needed to do something like $${\displaystyle \sum_{i=1}^{\pi(n)}\log p_{i}\geq\sum_{i=\lfloor\pi(n)/2\rfloor}^{\pi(n)}\log p_{i}\geq\frac{\pi(n)}{2}\cdot\log p_{\frac{\pi(n)}{2}}} ,$$ and then if I show that $\log p_{\frac{\pi(n)}{2}}=O(\log n)$ then I can prove what I need, but I didn't manage to. I am kinda out of ideas right now. Any clues people?

share|cite|improve this question
This is the Prime Number Theorem. Do you need hints or an answer? I'd say there are plenty of both online – Brent J Mar 24 '13 at 22:39
When I searched some through the net ive found many proofs, but none of them was elementary. The point in my question is to prove it using what I proved in the first exercise. I think it should be pretty elementary. If you have any hints on what I can do from here it will be very helpful. – John Smith Mar 24 '13 at 22:45
I'm not sure how the sum of logs works in to the proof. I know Erdos did an elementary proof (I think there is some controversy or something) and Atle Selberg did an elementary proof. I would suggest trying to find the latter if no one ends up answering. An elementary proof is going to be pretty involved – Brent J Mar 24 '13 at 23:36
@BrentJ: This is much weaker than the prime number theorem. – Aryabhata Mar 29 '13 at 2:43
@Aryabhata you're absolutely right. Thanks for pointing that out – Brent J Mar 29 '13 at 3:07
up vote 3 down vote accepted

The function you have from the previous exercise is the Chebyshev function. Let us call it $A(x)$.

You can now use Abel's identity to prove what you are seeking.

You have already shown

$$ \sum_{1 \lt k \le x} a(k) = A(x) \le cx$$

(where $a(x) = \log x$ if $x$ is prime, and $0$ otherwise)

(look at the Abel's Identity link to understand the choice of notation)

To use Abel's theorem, we take $f(x) = \frac{1}{\log x}$

And get

$$ \pi(x) = \sum_{1 \lt k \le x} \frac{a(k)}{\log k} \le \frac{cx}{\log x} + \int_{2}^{x} \frac{c}{\log ^2 t}\text{d}t = O\left(\frac{x}{\log x}\right)$$

Note: What you are trying to prove is much weaker than the prime number theorem.

share|cite|improve this answer

Of course partial summation is the most instructive way of doing this. However here is another answer which does not depend on anything:

Assuming that we have proved $$\sum_{p \leq x} \log p \leq C x,$$ for some positive constant $C>0$ and all $x >1,$ we have $$\Big(\pi(x)-\pi(x^{\frac{1}{2}}) \Big)\log(x^{\frac{1}{2}}) \leq \sum_{x^{\frac{1}{2}}<p\leq x} \log p \leq C x.$$ Now using the trivial bound $\pi(x^{\frac{1}{2}})\leq x^{\frac{1}{2}},$ we get that $$\pi(x)\leq 2C \frac{x}{\log x}+x^{\frac{1}{2}} =O(\frac{x}{\log x}). $$

share|cite|improve this answer

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.