- 15
- 0
Is there any mathematical formula to predict / generate / or test the prime number??
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].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.
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.you're better off doing what HallsofIvy proposes and trying to divide by all primes up to [itex]\sqrt{n}[/itex].
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.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.