# Elementary (high school-level) estimate of the number of prime numbers

Let $$\pi(x)$$ be a prime-counting function (the function counting the number of prime numbers less than or equal to some real number $$x$$. For example $$\pi(5)=3$$, $$\pi(4)=2$$). Prove by elementary (high school-level) methods that there is a function $$f: \mathbb{N} \to \mathbb{R}$$ and there is $$N_0 \in \mathbb{N}$$ such that for all $$n \ge N_0$$ the inequality $$\pi(n) \ge f(n)$$ holds and $$\lim \limits_{n \to \infty} \frac{f(n)}{\sqrt{n}}=\infty$$.

My work. Well known that $$\pi(n) > \frac{n}{\ln n}$$. But the proof of this inequality is not elementary (high school-level). I searched, but did not find other estimate. For example, it would be a good idea to prove that $$\pi(n) \ge n^{0.6}$$ for all $$n \ge N_0$$.

• I ask about the argument which would be accessible to a high school student (olympiad problem). – Witold Jul 5 '19 at 21:18
• @XanderHenderson I think for the OP "elementary" means "not advanced" and "school" means "not university". The former does not modify the latter. – Ethan Bolker Jul 5 '19 at 21:24
• OK :) Not a university, but a very advanced school. – Witold Jul 5 '19 at 21:27
• The Chebyshev bound mentioned here is both elementary and strong enough for your requirements. – Momo Jul 5 '19 at 21:47
• @Momo thank you very much! – Witold Jul 6 '19 at 12:30

Here's a funny bound: $$\forall m \geq 4 ,\pi(m) \geq \lfloor \log_2(\log_2(m)) \rfloor+1$$. It's not a very good bound at all, but it does follow a very easy argument, akin to the usual proof of that there are infinitely many primes.
First, we use the easy-to-show fact that there must be another prime $$p_2 < p_1^2 = 4$$
Then, we generalize this, saying that there must be another prime $$p_{n+1} < \prod_{k=1}^np_k$$ And from our base cases $$p_1=2$$, $$p_2<2^2$$, we can apply this formula to get for that for $$n \geq 1$$, we have $$p_{n} < 2^{(2^{n-1})}\implies \log_2\log_2(p_n)+1 And finally this tells us that $$\forall m\geq 4(>p_2)$$, we have our funny bound!
If one proves/accepts Bertrand's postulate (that $$\forall n>3, \exists p$$ s.t. $$p$$ is prime and $$n < p < 2n$$), then one can use a similar argument to get a slightly less silly bound around $$\log_2(n)$$.