4

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.

HunderingThooves
  • 962
  • 8
  • 20
  • 33
  • See sieve of Eratosthenes. May be more useful if you need to repeat the operation. – Ed Heal Aug 26 '11 at 13:35
  • Are we talking runtime computation or compile time computation? – Flexo Aug 26 '11 at 13:36
  • Reject even numbers from start. Only do the modulo test against odd numbers. Halved your computations, yay! – Nicolas Repiquet Aug 26 '11 at 13:38
  • See: http://stackoverflow.com/questions/2385909/most-elegant-way-to-write-isprime-in-java – Bart Kiers Aug 26 '11 at 13:39
  • 1
    Do you really want the fastest (of course I assume you mean runtime complexity with that), or just a fast one without any complex math? For the fastest, you could use some of the AKS class of the prime number tests. – PlasmaHH Aug 26 '11 at 13:40
  • I'm really open to anything, I'm just thinking of interesting ways to solve the problem – HunderingThooves Aug 26 '11 at 13:54
  • btw.: Checking a number, whether it is prime, and searching for a prime, are different things. For example, if you seach for a prime, take 2. Not two primes, but 2 as a prime. :) If you have to additional restrictions, you have to name them. – user unknown Aug 27 '11 at 07:42
  • Fastest or correct - who cares? But You should return return 'true' for number 2. – user unknown Aug 27 '11 at 08:53

5 Answers5

10

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.
Pieter
  • 17,435
  • 8
  • 50
  • 89
harold
  • 61,398
  • 6
  • 86
  • 164
3

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.

john
  • 85,011
  • 4
  • 57
  • 81
  • This function gives the wrong result for the numbers 1, 2, and 3. – Blastfurnace Aug 26 '11 at 16:47
  • 1
    this algorithm is not accurate, I don't know why it even has 3 upvotes. 25 and 35 are not a primes yet your algorithm says it's a prime and even more. please consider to update this. – Ousmane D. Feb 26 '17 at 20:33
2

Wikipedia has a pretty good article on that:

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

leifg
  • 8,668
  • 13
  • 53
  • 79
1

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;
}
Sylvain Cleymans
  • 1,829
  • 16
  • 13
  • 1
    more than that you can just test for prime values :D – Ricky Bobby Aug 26 '11 at 13:38
  • Except that it wouldn't work for x == 2, this is still extremely inefficient. – jarnbjo Aug 26 '11 at 13:38
  • @jambjo first line : if(x % 2 == 0) return false; – Ricky Bobby Aug 26 '11 at 13:41
  • It's a mistake. 2 is prime so it should return true. I have edited my code. – Sylvain Cleymans Aug 26 '11 at 13:42
  • @ricky: Ackar exactly. The original test claimed that 2 is not prime. Ackar just edited his response, but the code is still incorrect. Now it claims all even numbers to be prime. – jarnbjo Aug 26 '11 at 13:44
  • @jambjo , yep missunderstood the return false (I don't know why I thought it meant it's prime if it's equal to 2). So yep you're right. The first test should be if(x == 2) return true then test all odd number only . the code is still wrong – Ricky Bobby Aug 26 '11 at 13:48
1

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?)

Community
  • 1
  • 1
Ricky Bobby
  • 7,490
  • 7
  • 46
  • 63