It is suprisingly easy and pretty to give an elementary proof that the prime number theorem (that the number of primes less than is asymptotic to ) is true up to a constant factor. (I will address only the part where we show that there are many (i.e. at least ) primes less than .)

Consider a binomial coefficient . Let be a prime. We first want to know what the largest power of is which divides . There is more than one way to express the answer, the most elegant one I know of is as follows:

Add the numbers and in base (by the usual primary school algorithm). Then the number of carries that occur in this addition is equal to the greatest power of dividing .

What is most important for us is the fact that this number is no more than .

We immediately get

which is of course equivalent to

Make a good choice of and we are within a constant factor of the prime number theorem!