Algorithm for finding a prime with the least amount of computations

Question

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

Answer 1

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.

1. x smaller than 9: Return (x & 1) != 0 || x == 2
2. x smaller than about 200 (tweakable): use trial division (what you used)
3. x smaller than 1373653: use Miller Rabin with bases 2 and 3.
4. x smaller than 4759123141 (that is everything else): use Miller Rabin with bases 2, 7 and 61.

Answer 2

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.