Prime number.

  • Thread starter .physics
  • Start date
15
0
Is there any mathematical formula to predict / generate / or test the prime number??
 

Hurkyl

Staff Emeritus
Science Advisor
Gold Member
14,845
17
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

Science Advisor
Homework Helper
41,732
885
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.
 

CRGreathouse

Science Advisor
Homework Helper
2,817
0
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.
 
906
2
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.
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.
 

CRGreathouse

Science Advisor
Homework Helper
2,817
0
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 [itex]\sqrt{n}[/itex].
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.
 
154
0
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.
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.
 
1,056
0
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.
 

Related Threads for: Prime number.

  • Last Post
Replies
1
Views
2K
  • Last Post
2
Replies
28
Views
6K
  • Last Post
Replies
24
Views
6K
  • Last Post
2
Replies
44
Views
11K
  • Last Post
Replies
6
Views
4K
  • Last Post
Replies
10
Views
3K
  • Last Post
Replies
10
Views
3K
  • Last Post
Replies
6
Views
2K
Top