Prime number theorem - Simple English Wikipedia, the free encyclopedia

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).^[1]

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.