Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prime number.

  1. Aug 28, 2010 #1
    Is there any mathematical formula to predict / generate / or test the prime number??
  2. jcsd
  3. Aug 28, 2010 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I'm not sure precisely what you mean, but the answer is probably yes.

    However, algorithms are generally far easier to understand and efficient in practice than trying to compute an arithmetic formula.
  4. Aug 28, 2010 #3


    User Avatar
    Science Advisor

    Certainly there exist a formula for testing form prime numbers:
    To determine whether n is a prime number, divide it by every prime less than or equal to [itex]\sqrt{n}[/itex]. If none of those divides n, then n is prime.
  5. Aug 28, 2010 #4


    User Avatar
    Science Advisor
    Homework Helper

    Sure there are primalitry tests. To see if an integer n is prime, calculate [itex]\pi(n)-\pi(n-1)[/itex]. The result is 1 if an only if the number is prime.
  6. Aug 28, 2010 #5
    but since the fastest algorithm to calculate [itex]\pi(n)[/itex] that, to my knowledge, has ever been actually implemented and tested, is O([itex]n^{2/3}[/itex] times some logs), you're better off doing what HallsofIvy proposes and trying to divide by all primes up to [itex]\sqrt{n}[/itex].

    Beyond that, there is an algorithm based on Little Fermat's theorem that will either tell you that your number is composite or give you a very high probability that it's not.
  7. Aug 28, 2010 #6


    User Avatar
    Science Advisor
    Homework Helper

    I suppose this means my example wasn't sufficiently over-the-top. New suggestion: to test if n is prime, test if sigma(n^2) = n^2 + n + 1.

    Far better would be APR-CL, and better than that would be ECPP. Eventually, AKS will be better than either, but that's not likely to happen soon or for small numbers.
  8. Aug 31, 2010 #7
    This trial division method is certainly the easiest method; although it becomes difficult to compute for very large values of n. A similar variation on the trial division is to test whether n is a multiple of another integer m that is between 2 and the [tex]\sqrt{n}[/tex]. Obviously, if this is true than n is composite.
  9. Sep 1, 2010 #8
    Mersenne primes have been extensively studied, and some are generally among the largest primes known. The form is 2^p -1. p must be prime and in this case a factor of the number, if it exists, is of the form 2kp+1, and is +/- 1 Mod 8. This eliminates a whole lot of cases!

    In fact in the case of 2^13-1 =8197, for 26k+1 to be of the form +/-1 Mod 8 , we have k=3 and k=4, giving 79 and 105the second case is eliminated since it contains 5 not of the form, while 79 can be shown not to work. Since the square root of 8191 is 90.5.., we need not try k=7 or higher, SO 2^13-1 IS A MERSENNE PRIME.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook