# Using sum of logarithms of primes to prove the number of primes up to $n$ is $O(n/\log n)$

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?

-
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

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.

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

-

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

-