The idea for this post arose from this quora answer.
Let denote the number of primes up to . It is well-known that
which is the celebrated prime number theorem. Although “elementary” proofs exist, most proofs of the prime number theorem are technical. Nevertheless, we can obtain some simple bounds as follows.
Let denote fixed prime numbers . By the inclusion-exclusion principle, the number of positive integers not divisible by any of the is
Therefore, we have the following (rather weak) bound for the prime-counting function :
This implies the following result.
For example, let’s say we want to find all such that at least 20% of the natural numbers below are prime. Then
If are the prime numbers , then this means that
The left-hand side is positive for , for which the inequality has the solution . Trying the values in this range we obtain the following set of solutions
In general, if we want to find all such that , then we start by finding the least such that the -th prime satisfies
(Note that such a is guaranteed to exist since the left-hand side approaches as , since the harmonic series diverges.) Then we can bound using
(Observe also that is prime.)