Prime Numbers: A Mathematical Mystery

[.physics]

Is there any mathematical formula to predict / generate / or test the prime number??

 

[Hurkyl]

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.

 

[HallsofIvy]

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 \sqrt{n}. If none of those divides n, then n is prime.

 

[CRGreathouse]

Sure there are primalitry tests. To see if an integer n is prime, calculate \pi(n)-\pi(n-1). The result is 1 if an only if the number is prime.

 

[hamster143]

Sure there are primalitry tests. To see if an integer n is prime, calculate \pi(n)-\pi(n-1). The result is 1 if an only if the number is prime.

but since the fastest algorithm to calculate \pi(n) that, to my knowledge, has ever been actually implemented and tested, is O(n^{2/3} times some logs), you're better off doing what HallsofIvy proposes and trying to divide by all primes up to \sqrt{n}.

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.

 

[CRGreathouse]

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.

you're better off doing what HallsofIvy proposes and trying to divide by all primes up to \sqrt{n}.

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.

 

[sEsposito]

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 \sqrt{n}. If none of those divides n, then n is prime.

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 \sqrt{n}. Obviously, if this is true than n is composite.

 

[robert Ihnot]

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.