The stroke calculation algorithm with the least number of calculations

Question

Assuming you're going to write a function / method to search for a prime, what would be the most efficient way to do this? I think this will be a test that looks something like this:

Code below in semi-C ++

bool primeTest (int x) { //X is the number we're testing int testUpTo = (int)((sqrt(x))+1); for (int i=3; i<testUpTo; i+=2){ if ((x%i)==0) { return false; } } return true; } 

Does anyone have a better way to solve this that would require less computation?

Edit: Changed the code a bit, twice. I did not write this in the light of any particular language, although I believe that it is C ++ over java due to the word bool.

Answer 1

I would use the Miller Rabin test, which can be easily determined for numbers less than 341 550 501 728 321 (and 2 ^ 31 is much less than this).

Pseudo-code: There are several different cases.

• x less than 9: Return (x & 1) != 0 || x == 2 (x & 1) != 0 || x == 2
• x less than about 200 (configurable): use trial division (what you used)
• x less than 1373653: use Miller Rabin with bases 2 and 3.
• x less than 4759123141 (that's all else): use Miller Rabin with bases 2, 7 and 61.

Answer 2

In addition to 2 and 3, all primes are one more or less than a multiple of six. Using this fact will improve your code. Something like this (untested)

 bool primeTest (int x){//X is the number we're testing if (x == 1) return false; if (x == 2 || x == 3) return true; if(x%2 == 0 || x%3 == 0) return false; int testUpTo = (int)((sqrt(x))+1); for(int i=6; i<testUpTo; i+=6){ if ((x%(i-1))==0 || x%(i+1)==0){ return false; } } return true; } 

Of course, for many centuries advanced mathematics have tried to find more effective tests for primacy.

Answer 3

Wikipedia has a pretty good article:

http://en.wikipedia.org/wiki/Primality_test

Answer 4

You can improve code testing with only odd values.

 bool primeTest (int x){//X is the number we're testing if(x == 2) return true; int testUpTo = (int)((sqrt(x))+1); for(int i=3; i<testUpTo; i+=2){ if ((x%i)==0){ return false; } } return true; } 

Answer 5

You can take a look at this article, which tests the performance of various primary tests:

BENEFITS OF THE SOURCE OF LIFE Richard P. Brent: http://cs.anu.edu.au/student/comp4600/lectures/comp4600_primality.pdf

(see this other post: What is the fastest determinate primitiveness criterion for numbers ranging from 2 ^ 1024 to 2 ^ 4096? )