Here’s an elegant proof from Paul Erdős that there are infinitely many primes. It also does more, giving a lower bound on π(N), the number of primes less than N.
First, note that every integer n can be written as a product n = r s2 where r and s are integers and r is square-free, i.e. not divisible by the square of any integer. To see this, let s2 be the largest square dividing n and set r = n / s2.
Next we over-estimate how many r s2 factorizations there are less than or equal to N.
How many square-free numbers are there less than or equal to N? Every such number corresponds to a product of distinct primes each less than or equal to N. There are π(N) such primes, and so there are at most 2π(N) square-free numbers less than or equal to N. (The number of subsets of a set with m elements is 2m.)
How many squares are there less than N? No more than √N because if s > √N then s2 > N.
So if we factor every number ≤ N into the form r s2 there are at most 2π(N) possibilities for r and at most √N possibilities for s. This means
2π(N) √N ≥ N
Now divide both sides of this inequality by √N and take logarithms. This shows that
π(N) ≥ log(N) / log 4
The right side is unbounded as N increases, so the left side must be unbounded too, i.e. there are infinitely many primes.
Euclid had a simpler proof that there are infinitely many primes. But unlike Euclid, Erdős gives a lower bound on π(N).
Source: Not Always Buried Deep