Elementary Methods in Number Theory Exercise 1.5.10

Prove that $\pi(n)\leq \frac{n}{2}$ for $n\geq 8$.


Proof:According to Eratosthenes's sieve method, when $n\geq 8$,$\sqrt{n}\geq 2$.Then we delete all the multiples of the prime number 2(except 2 itself),and we delete 1.The number of the multiples of 2 (except 2)is $[\frac{n}{2}]-1$,so $\pi(n)\leq (n+1-[\frac{n}{2}])-1$.When $n$ is even,then $\pi(n)\leq \frac{n}{2}$.When $n$ is odd,then $\pi(n)\leq \frac{n-1}{2}\leq\frac{n}{2}$.

原文地址:https://www.cnblogs.com/yeluqing/p/3827599.html