History of primes

Whether the Babylonians had the notion of primes is not clear, but before 400 BC the Pythagoreans had introduced primes as numbers of objects that can be arranged only in a single line, and not in any other rectangular array. Around 300 BC Euclid discussed various properties of primes in his Elements, giving for example a proof that there are an infinity of primes. The sieve of Eratosthenes was described in 200 BC, apparently following ideas of Plato. Then starting in the early 1600s various methods for factoring were developed, and conjectures about formulas for primes were made. Pierre Fermat suggested 2²ⁿ + 1 as a source for primes and Marin Mersenne 2^Prime[n] - 1 (see page 911). In 1752 Christian Goldbach showed that no ordinary polynomial could generate only primes, though as pointed out by Leonhard Euler n² - n + 41 does so for n < 40. (With If or Floor included there are at least complicated cases known where polynomial-like formulas can be set up whose evaluation corresponds to explicit prime-generating procedures—see page 1162.) Starting around 1800 extensive work was done on analytical approximations to the distribution of primes (see below). There continued to be slow progress in finding specific large primes; 2³¹ - 1 was found prime around 1750 and 2¹²⁷ - 1 in 1876. (2²⁵ + 1 was found composite in 1732, as have now all 2²ⁿ + 1 for n ≤ 32.) Then starting in the 1950s with the use of electronic computers many new large primes were found. The number of digits in the largest known prime has historically increased roughly exponentially with time over the past two decades, with a prime of over 4 million digits (2^13466917 - 1) now being known (see page 911).