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.

That is a very useful animation that demonstrates how to identify primes!

Pierre de Fermat, for instance, conjectured that [x] is prime, but Euler proved that [y] is composite.

Should those be:

x:

all 2^(2^n)+1

y:

2^32+1

Your statement that no polynomial exists which can only generate prime numbers is only partially true. There exist multivariable polynomials which generate only prime numbers when the input variables range over non-negative integers. See here for an example – http://en.wikipedia.org/wiki/Formula_for_primes#Formula_based_on_a_system_of_Diophantine_equations

Thank you. Maybe I made a mistake. I mean that no polynomial exists that can generate all prime numbers.

Hello Guillermo,

There is a way of obtaining the polynomial using the stirling numbers of the second kind restriction 2. Would you please check the article and give me your feedback?

http://marianoalvarolauria.blogspot.com.es/2014/06/stirling-numbers-pascals-triangle-and.html

Best regards,

Mariano