# Prime Number Theorem

The list of prime numbers suggests that they thin out the further you go: 44% of the one-digit numbers are prime, but only 23% of the two-digit numbers and 16% of the three-digit numbers. The trial division method provides an intuitive explanation. To test whether a number is prime, you have to try whether it can be divided by all numbers between 2 and . Large numbers have to undergo more tests, so fewer of them will be prime.

The **Prime Number Theorem** explains how fast the prime numbers thin out. It says that if you are looking around the number , about one in every numbers is prime (here, denotes the natural logarithm of ). The formal statement of the Prime Number Theorem is

where denotes the number of primes . This result was demonstrated independently by Jacques Hadamard and Charles de la Vallée Poussin in 1896. An essential part of their proof is the function

This function was already considered by the 18th century Swiss mathematician Leonhard Euler, who realized that

where the product on the right goes over all prime numbers:

To see why this is so, we use the formula for the sum of a geometric series to write the product as

Multiplying out this product, we get a sum of terms of the form

where , ..., are prime numbers and , ..., are positive integers. Euler's formula equating the sum and the product now follows from the fact that every number has a unique factorization into primes. This also indicates the connection between the function and the prime numbers.

Euler used his formula to give an alternative proof that there are infinitely many primes. If we take , we get

The sum on the left is the harmonic series, which diverges. If the number of primes were finite, then the product would evaluate to a finite number. This contradiction shows that there are infinitely many primes.

The above definition for the function only works when , because the infinite sum diverges otherwise, but a technique called analytic continuation can be used to extend the definition to all values of , including complex numbers. The function with the extended domain is known as the Riemann zeta function. Hadamard and de la Vallée Poussin proved that this function cannot be zero in certain parts of the complex plane and used this to establish the prime number theorem. A proof not relying on complex analysis proved elusive, even though weaker results on the distribution of prime numbers have long been known^{[1]}^{[2]}. It was only in 1949 that Atle Selberg and Paul Erdős were able to establish the theorem by elementary means.