Prime number theorem

The prime number theorem is a theorem from number theory. Prime numbers are not distributed evenly across the number range. The theorem formalizes the idea that the probability of hitting a prime number between 1 and a given number becomes smaller, as numbers grow. This probability is about n/ln(n), where ln(n) is the natural logarithm function. This means that the probability of hitting a prime number with 2n digits is about half as likely than with n digits. For example, among the positive integers of at most 1000 digits, about one in 2300 is prime (ln 10¹⁰⁰⁰ ≈ 2302.6), whereas among positive integers of at most 2000 digits, about one in 4600 is prime (ln 10²⁰⁰⁰ ≈ 4605.2). In other words, the average gap between consecutive prime numbers among the first N integers is roughly ln(N).

Fifteen-year old Carl Friedrich Gauss suspected that there was a link between prime numbers and logarithms in 1793. Adrien-Marie Legendre also suspected such a link in 1798. Jacques Hadamard and Charles-Jean de La Vallée Poussin proved the prime number theorem in 1896, over a century after Gauss.

Prime Number Theorem Media

• 

  Graph showing ratio of the prime-counting function π(x) to two of its approximations, x / log x and Li(x). As x increases (note x axis is logarithmic), both ratios tend towards 1. The ratio for x / log x converges from above very slowly, while the ratio for Li(x) converges more quickly from below.

• 

  Log-log plot showing absolute error of x / log x and Li(x), two approximations to the prime-counting function π(x). Unlike the ratio, the difference between π(x) and x / log x increases without bound as x increases. On the other hand, Li(x) − π(x) switches sign infinitely many times.

• 

  Graph comparing π(x) (red), x / log x (green) and Li(x) (blue)

• 

  Plot of the function \ \pi(x;4,3)-\pi(x;4,1) \ for n ≤ 30000