Upper bound for prime-counting function: $ \pi(n)\le\frac{n}{3}+2 $ $ \pi(n)\le\frac{n}{3}+2 $... Could someone explain me, how to prove it? I'm completely stuck, as informations I found on Wikipedia aren't very clear to me. (I was able to prove that for sufficiently large $ n $, $ \pi(n)\le\frac{n}{2} $, but this one seems harder). Thank you in advance. 
 A: Hint: Exepted for 2 and 3, primes are always congruent to 1 or 5 mod 6. 
To prove this, we see that if it is 0,2,4 mod 6, it is divisible by 2, and if its 3 mod 6 its divisible by 3. 
A: As you know (I hope :),
$$\pi(n)\sim \frac{n}{\ln n};$$
so, you can say that $\pi(n)<n/k$ for any $k>1$ for sufficiently large $n$.
But asymptotic behavior of $\pi(n)$ doesn't matter. For any integer $K>1$ and any prime $p$ we must have $\gcd(p, K)=1$ (if $K$ is not equal to some prime, of course, but in this case $\gcd(p,K)\ne 1$ only for one number). Hence, there is not greater than $$\frac{\varphi(K)}{K}n$$
prime numbers $< n$ for large $n$ (where $\varphi(K)$ is Euler's phi function). (For $K=6$ $\varphi(6)=2$, and we get you upper bound.) Since
$$
\frac{\varphi(K)}{K} = \prod_{p_i\mid K} \left(1-\frac1p_i\right),
$$
$\varphi(K)/K$ can be smaller than any positive real number.
A: We can use the Legendre-Eratosthenes inequality $$\pi\left(x\right)-\pi\left(z\right)\leq\sum_{d\mid P\left(z\right)}\mu\left(d\right)\left[\frac{x}{d}\right]
 $$ where $$P\left(z\right)=\prod_{p\leq z}p,\, z\in\left[2,x^{1/2}\right].
 $$ Then, taking $z=5
 $ and $n
 $ sufficiently large we have $$\pi\left(n\right)\leq\sum_{d\mid30}\mu\left(d\right)\left[\frac{n}{d}\right]+3$$ $$=n-\left[\frac{n}{2}\right]-\left[\frac{n}{3}\right]-\left[\frac{n}{5}\right]+\left[\frac{n}{6}\right]+\left[\frac{n}{10}\right]+\left[\frac{n}{15}\right]-\left[\frac{n}{30}\right]+3\leq\frac{4n}{15}+7\tag{1}
 $$ using the inequality $$\left[x\right]\geq x-1
 $$ and obviuously, if $n
 $ is large we have $$\frac{4n}{15}+7\leq\frac{n}{3}+2.
 $$
