Prime Number Formula

Date: 11/11/2001 at 18:10:27
From: Ri
Subject: Prime number formula

I have to find out the formula Leonhard Euler used to find prime 
numbers.  I just need the formula so I can put it into a spreadsheet.  

Thank you.

Date: 11/11/2001 at 19:21:56
From: Doctor Paul
Subject: Re: Prime number formula

Following is a somewhat celebrated result of Euler:

The function f(x) = x^2 + x + 41 is prime for x = 0, 1 ,..., 39

f(41) is obviously not prime because 
f(41) = 41^2 + 41 + 41 = 41 * (41 + 1 + 1)

f(40) = 40^2 + 40 + 41

But notice that another way to write 40^2 is:

40^2 = 40^2 + 2*40 + 1 - 2*40 - 1 = (40 + 1)^2 - 2*40 - 1

Then 

f(40) = 40^2 + 40 + 41 = (40 + 1)^2 - 2*40 - 1 + 40 + 41 = 41^2

hence f(40) isn't prime either.

This quadratic was the record holder for centuries as a consecutive, 
distinct quadratic prime-producer for an initial range of input 
values. It is not, however, the current record holder. That 
distinction goes to the function:

f(x) = 36x^2 - 810x + 2753 

which is prime for x = 0, 1, ... , 44

I do not know who this result is attributed to.

For more, see the June/July issue of "The American Mathematical 
Monthly" (any university library will have it) for an article entitled 
"Prime-Producing Quadratics," by Richard Mollin.

- Doctor Paul, The Math Forum
  http://mathforum.org/dr.math/