General Formula to Find Prime Numbers?

Date: 10/12/2005 at 22:24:39
From: Swapnil
Subject: General Formula To Find Prime Numbers?

Hi Dr. Math, 

I was wondering if it is *possible* that there exists a general
formula to know what numbers are prime, or has it been *proven*
that no such formula could exist? 

What evidence do we have for either case?

Thanks for your kind help,

- Swapnil

Date: 10/13/2005 at 10:26:55
From: Doctor Vogler
Subject: Re: General Formula To Find Prime Numbers?

Hi Swapnil,

Thanks for writing to Dr. Math.  It depends on what you mean by
"formula."  For example, I might ask you if there is a "formula" for
the cosine of a number.  You would probably say, "Of course!  It is
'cos x.'"  But that is simply dodging the question.  In like manner,
many people write p_n (p with a subscript n) to mean the n'th prime. 
But that's dodging your question.  You'll find this notation in

  Prime Number
    http://mathworld.wolfram.com/PrimeNumber.html 

where you'll also find the wonderful quote:

  In a 1975 lecture, D. Zagier commented "There are two facts about
  the distribution of prime numbers of which I hope to convince you so
  overwhelmingly that they will be permanently engraved in your
  hearts.  The first is that, despite their simple definition and role
  as the building blocks of the natural numbers, the prime numbers
  grow like weeds among the natural numbers, seeming to obey no other
  law than that of chance, and nobody can predict where the next one
  will sprout.

  The second fact is even more astonishing, for it states just the
  opposite: that the prime numbers exhibit stunning regularity, that
  there are laws governing their behavior, and that they obey these
  laws with almost military precision" (Havil 2003, p. 171).

If you mean an algorithm, then yes, there are certainly algorithms for
finding prime numbers.  In fact, if you search the Internet, you'll
find prime number generators available for free download that can
generate prime numbers faster than your hard drive can record the list
(so they typically won't store them all to disk).  Such programs are
not hard to write.  One very efficient algorithm is the Sieve of
Eratosthenes, which has been around for over 2000 years.  You can
search our archives for lots of answers about the Sieve of
Eratosthenes by going to our search engine and entering "Sieve of
Eratosthenes":

    http://mathforum.org/library/drmath/mathgrepform.html 

But if you mean a polynomial or some other simple formula, then no,
there is no such formula.  I am quite sure it has been proven that
there is no polynomial whose values are exactly the prime numbers.  If
you want a similar proof for other kinds of simple formulas, then you
need to specify what kinds of formulas you are talking about.  (For
example, you want to make sure you rule out things like p_n and
related functions.)

But there are formulas for prime numbers, and sums of prime numbers,
and sums of their logs, and such things, that have to do with
complicated transcendental functions like the Riemann Zeta Function

  Riemann Zeta Function
    http://mathworld.wolfram.com/RiemannZetaFunction.html 

and sums over the zeros of the Riemann Zeta Function, and such things.
This function is used in proving the Prime Number Theorem:

  Prime Number Theorem
    http://mathworld.wolfram.com/PrimeNumberTheorem.html 

If you have any questions about this or need more help, please write
back and show me what you have been able to do, and I will try to
offer further suggestions.

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