Algorithm for finding a prime with the least amount of computations
Assuming you were going to write a function / method to find a prime number, what would be the most efficient way to do this? I'm thinking that it would be a test that is 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 so开发者_如何学Gomeone have a better way to go about solving this that will take less computations?
edit: Changed code slightly, twice. I didn't write this with any specific language in mind, although I suppose it's C++ over java due to the word bool.
I would use the Miller Rabin test, which can easily be made deterministic for numbers smaller than 341,550,071,728,321 (and 2^31 is much smaller than that).
Pseudocode: there are a number of different cases.
x
smaller than 9: Return(x & 1) != 0 || x == 2
x
smaller than about 200 (tweakable): use trial division (what you used)x
smaller than 1373653: use Miller Rabin with bases 2 and 3.x
smaller than 4759123141 (that is everything else): use Miller Rabin with bases 2, 7 and 61.
Apart from 2 and 3, all prime numbers are one more or one less than a multiple of six. Using that fact would 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 there has been centuries of advanced mathematics to try and find more efficient primality tests.
Wikipedia has a pretty good article on that:
http://en.wikipedia.org/wiki/Primality_test
You can have a look at this paper who test the performance of different primality tests :
PRIMALITY TESTING by Richard P. Brent: http://cs.anu.edu.au/student/comp4600/lectures/comp4600_primality.pdf
(see this other post : What is the fastest deterministic primality test for numbers in the range 2^1024 to 2^4096?)
You can improve your code testing 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;
}
精彩评论