Associated Topics || Dr. Math Home || Search Dr. Math

### 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?

- 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

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
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
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

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/
```
Associated Topics:
College Number Theory
High School Number Theory
Middle School Prime Numbers

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search