- #1

- 15

- 0

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

- Thread starter .physics
- Start date

- #1

- 15

- 0

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

- #2

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

- 14,916

- 19

However, algorithms are generally far easier to understand and efficient in practice than trying to compute an arithmetic formula.

- #3

HallsofIvy

Science Advisor

Homework Helper

- 41,833

- 956

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.

- #4

CRGreathouse

Science Advisor

Homework Helper

- 2,820

- 0

- #5

- 907

- 2

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.

- #6

CRGreathouse

Science Advisor

Homework Helper

- 2,820

- 0

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].

- #7

- 154

- 0

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.

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.

- #8

- 1,056

- 0

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.

- Last Post

- Replies
- 1

- Views
- 2K

- Last Post

- Replies
- 28

- Views
- 7K

- Last Post

- Replies
- 24

- Views
- 6K

- Last Post

- Replies
- 44

- Views
- 11K

- Last Post

- Replies
- 6

- Views
- 2K

- Last Post

- Replies
- 10

- Views
- 3K

- Last Post

- Replies
- 6

- Views
- 4K

- Last Post

- Replies
- 10

- Views
- 3K

- Last Post

- Replies
- 14

- Views
- 8K

- Last Post

- Replies
- 11

- Views
- 3K