The Polynomials that Generate Prime Numbers

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. 

Sieve of Eratosthenes Generates Prime Numbers

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 2^{2^2} + 1 is prime, but Euler proved that 2^{32} is composite.  Primes of such form are now known as Fermat’s Prime.

Legendre also gave the polynomial 2n^2 + 29 which is prime from n=0 to n=28 but fails for n = 29 and n^2 + n + 17 which is prime from n = 0 to n = 15.

The most famous polynomial prime generator (probably) was Euler’s n^2 - n + 41 which is prime from n = 0 to 40, but fails for n = 41. Another polynomial n^2 - 79n + 1601 given by E.B. Escott is prime for all n = 0, 1, 2, 3, ... , 79. There are also more polynomials that  generate primes, the most complicated of which perhaps is


This gives prime numbers from n = 0 to n = 56.

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.

Leave a Reply