20050820, 12:52  #1 
2^{2}×23×41 Posts 
What is the significance of prime numbers?
Serious question, I'm just wondering what the big deal is with prime numbers... so they can't be divided.. is there something significant with that?
Also am I correct in the assumption that there is no real formula which can be used to find out all the prime numbers? other than using some math program which simply just attempts to divide the number to figure out if it's prime or not.. and also other than that 2n1 which only finds primes here and there...... is there a formula out there which will find each and every prime? 
20050820, 14:56  #2 
"GIMFS"
Sep 2002
Oeiras, Portugal
11·137 Posts 
If there were such formula, the search for Prime Numbers would be meaningless, don´t you think?...

20050820, 15:14  #3 
Jun 2005
Near Beetlegeuse
388_{10} Posts 
There is not a formula that will find every prime number, but there is a method. It’s called division. You simply divide your number by every prime lower than it, and if it divides your number is not prime.
The trouble with this approach is that for huge numbers it would take years – even with computers  to prove whether a number is prime or not. Mathematicians have therefore developed a lot of clever techniques for determining whether or not a number MIGHT be prime. They then concentrate their efforts – computer time costs money, after all  on those that might be prime. Numbers of the form (2^n)1 are called Mersenne numbers, and it can be shown that they MIGHT be prime if, and only if, n is prime. That n is prime does not, however, guarantee that (2^n)1 will be prime. (2^5)1 is prime, but (2^11)1 is not. There are other forms of numbers for which similar rules apply. As for the usefulness of prime numbers; do you have a mobile phone, or cash point card, or credit card, or have you ever bought anything over the internet? All of these transactions, and many other things you do every day, rely for their security on the simple fact that it is so hard to find prime numbers in a reasonable amount of time. In very simple terms, take any two prime numbers and multiply them together, and you have a security code that can only be broken with those same two original prime numbers. No other combination will work, ever. In part, that is why prime numbers are so useful, so important, and yet so tantalisingly elusive that searching for them would be interesting and satisfying even if they had no use at all. 
20050821, 00:33  #4 
Dec 2004
The Land of Lost Content
100010001_{2} Posts 
If it is a serious question and if you would like to read further on the subject, try Marcus du Sautoy's book: The Music of the Primes.

20050821, 00:48  #5 
May 2003
1547_{10} Posts 
There are plenty of formulas for giving us each and every prime. They are just usually very complicated, and require the computation of all previous primes.
As for the usefulness of prime numbers, one word: cryptography. 
20050821, 10:05  #6 
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}·3·641 Posts 
(For the sake of newbies) Regarding an apparent contradiction:
When some folks say there's no formula for finding every prime number, while other folks say there are formulas for every prime number ... they're both right ... sort of. What's happening is that there are different unstated assumptions in each case. As simple examples, let me offer these slightlyexpanded versions: There's no formula for finding every prime number that requires less work than what we usually think of as the standard nonformulaic methods for finding primes. There are formulas for computing every prime number but they require that previous primes have already been found and/or offer no overall shortcut in the amount of work required. Each of those could be stated more rigorously, and there are even more unstated conditions and assumptions that could be added to each. I'll stop here. 
20050821, 12:27  #7 
Jun 2003
The Texas Hill Country
3^{2}×11^{2} Posts 
Do you mean "formula" or "algorithm" ? They are not the same.

20050821, 13:08  #8 
Oct 2004
23^{2} Posts 
A "formula"?
"If there were such formula, the search for Prime Numbers would be meaningless, don´t you think?... "
NO, I dont think so (and suspect your wink is made knowingly) As for the suggestion to read "Music of the primes" More specifically see p199/p200 where there is an explicit formula presented which will generate all primes without missing any at all. I agree with Wacky that you might also call it an "algorithm" or means for finding primes, as it also generates 0 or negative values which are answers to be ignored. Any positive result is prime. I quote from du Sautoy: "But could mathematicians find such a formula? In 1971, Matijasevich devised an explicit method for arriving at such a formula, but he did not follow it through to produce an answer. The first explicit formular to be written out in detail used 26 variables A to Z and was discovered in 1976:" It is reproduced and I did type it for you but lost the post :( However as has been pointed out, to use it would be a lot of work! So, it may not be of practical use, but I found it interesting to read that such a formula did indeed exist! As for significance, being prime tells us that a number can't be divided without a remainder. Thus if I had a prime number of (whatever) I could not share them fairly among members of my family or friends (assuming number of people < the prime). eg if I have 13 footballs, unless there are 1 or 13 people, I will have to start disecting footballs with a knife to share them, and that does tend to ruin them :) 
20050822, 08:48  #9  
"GIMFS"
Sep 2002
Oeiras, Portugal
11·137 Posts 
Quote:


20050822, 15:23  #10 
"Richard B. Woods"
Aug 2002
Wisconsin USA
1111000001100_{2} Posts 
From the MathWorld page for Formula: "In mathematics, a formula is a fact, rule, or principle that is expressed in terms of mathematical symbols. Examples of formulas include equations, equalities, identities, inequalities, and asymptotic expressions."
What I had in mind when I wrote "formula" was the sort of equation y = f(x) which gives prime values of y for some range of integer values of x. But the originator's question also makes sense when algorithm is substituted for formula. From the MathWorld page for Algorithm: "A specific set of instructions for carrying out a procedure or solving a problem, usually with the requirement that the procedure terminate at some point. Specific algorithms sometimes also go by the name method, procedure, or technique." Last fiddled with by cheesehead on 20050822 at 15:24 
20050822, 16:41  #11  
Nov 2003
2^{2}×5×373 Posts 
Quote:
lacking in rigor. However, I hope I can clarify and correct some of the incorrect claims that have been made. Formulae do exist that will give the n'th prime. However, such formulae are usually given as summations which require prohibitive calculation. See, for example, Paulo Ribenboim's "Book of Prime Number Records" Algorithms do exist for finding the n'th prime that are much better than finding them all. One applies a prime *counting* algorithm and then uses binary search. As for the "algorithm vs. formula" debate, allow me to say that the difference is often a matter of how much math you know. Suppose, for example, I state that the answer to some problem is "y = sin(x)". Most would accept this as a formula because they *recognize* what sin(x) is, even though to COMPUTE sin(x) requires an *algorithm*. However, if I said the answer is "y = H(a;b;x)/G(x)" where H is a hypergeometric function, and G is the gozinta function, many would not accept this as a "formula" because they do not recognize the functions. Especially if computing the functions requires a complicated and expensive algorithm. Both "formula" and "algorithm" are fuzzy concepts. However, under any reasonable interpretation, expressions that give the n'th prime as summations involving trig functions and the (say) factorial function ARE formula. Furthermore, closed form formulae exist for pi(n), but they are not elementary; they can be given in terms of contour integrals involving the zeta function. The most efficient to calculate was given by Odlyzko, Lagarias et.al. and requires good knowledge of complex function theory. But the formula itself is simple. Much of this is hard to explain to newbies because they lack the required background. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
What can you do with 2 prime numbers?  VicDiesel  Programming  12  20170420 21:16 
Prime Numbers Or Not  Arxenar  Miscellaneous Math  38  20130628 23:26 
All odd numbers are prime  Citrix  Lounge  5  20100405 21:34 
Another series of prime numbers ?  spkarra  Miscellaneous Math  3  20091229 00:23 
Prime numbers  Unregistered  Miscellaneous Math  8  20081109 07:45 