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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.