The search for primes started thousands of years ago. Mathematicians since antiquity tried to find ways to look for primes. They also searched for methods to test if a number is prime or not. Others tried to find polynomials to generate primes.
The Sieve of Eratosthenes
One of the ancient methods of listing prime numbers is the Sieve of Eratosthenes. The Sieve consists of a finite list of numbers, where the multiples of each number are crossed out starting from 2 and increasing each time the list is exhausted.
Using computers, this algorithm can be used to generate as many primes as possible given enough time and computer memory. However, despite its reliability, there is no way that we could list all primes because it has been proved that there are infinitely prime numbers.
Prime Generating Polynomials
Aside from the Sieve, mathematicians searched for other ways to generate prime numbers. Pierre de Fermat, for instance, conjectured that is prime, but Euler proved that is composite. Primes of such form are now known as Fermat’s Prime.
Legendre also gave the polynomial which is prime from to but fails for and which is prime from to .
The most famous polynomial prime generator (probably) was Euler’s which is prime from to , but fails for . Another polynomial given by E.B. Escott is prime for all . There are also more polynomials that generate primes, the most complicated of which perhaps is
This gives prime numbers from to .
Question: Is there a polynomial that will generate only prime numbers?
Answer: There is none. It has been proved that no polynomial exists can ever produce only primes.