2

Possible Duplicate:
Most Elegant Way to write isPrime in java

How do I go about making this faster or better? I made it to solve a project Euler problem then optimized it, but I'm sure it's not the best method 

public static boolean prime(int number){
    int limit = (int) (1 + Math.sqrt(number) );
    if (number < 1) return false;
    if (number == 2) return true;
    if (number % 2 == 0) return false;

    for(int i= 3; i < limit; i+=2)
        if(number % i == 0)
            return false;
    return true;
}
}
Community
  • 1
  • 1
Josh Horowitz
  • 655
  • 2
  • 6
  • 15
  • 1
    This is incorrect for 1 (1 is not prime, but the function will return true erroneously). – Platinum Azure Dec 16 '12 at 20:43
  • 1
    Was gonna point out the Math.sqrt(number) theoreme thingy but I see you already did that :-). Beyond this, I'd recommend checking out the answers for [this](http://stackoverflow.com/questions/453793/which-is-the-fastest-algorithm-to-find-prime-numbers) question. Although the question is specifically on C++, it shouldn't be too hard to transfer the logic over to Java (as you probably know, both are C-like). So doing some research on sieves of different kinds would probably be a good idea. – Priidu Neemre Dec 16 '12 at 20:45

4 Answers4

4

Except for its handling of the number 1, the function looks pretty good. One improvement that can be made is to make use of the fact that all primes greater than 3 are of the form 6k ± 1.

You can choose to go even further, but you'll have to balance improved performance with increased code complexity.

NPE
  • 486,780
  • 108
  • 951
  • 1,012
  • How would you implement that? – Frank Dec 16 '12 at 20:48
  • @Frank: Same as OP already does, only increase `i` in steps of `6` rather than `2`, and have two `ifs` instead of one. – NPE Dec 16 '12 at 20:49
  • @Frank You could modify your loop: `for (int i = 6; i < limit; i += 6) { int nn = i - 1; int pn = i + 1; // check both pn and nn }` – FThompson Dec 16 '12 at 20:50
  • This is a simple form of [wheel factorization](http://en.wikipedia.org/wiki/Wheel_factorization). It can be improved by using a larger "wheel" than 2 x 3. –  Dec 16 '12 at 20:58
  • @duskwuff what do you propose...show us some code – Frank Dec 16 '12 at 22:33
3

Depends on how fancy you want to get.

One easy improvement is to use wheel factorization -- instead of just trying every odd number (e.g, numbers which are not divisible by 2), try only numbers which are not divisible by several small primes. For instance, here's an implementation that checks for divisibility by 2 or 3:

for (int i = 6; i < limit; i += 6) {
    if (number % (i + 1) == 0) return false;
    if (number % (i + 5) == 0) return false;
}

This only has to do two tests for every six numbers, instead of the 1/2 your code does. You can improve it further by adding additional primes (the wheel on the Wikipedia article tests 8 out of 30), but at the expense of rapidly increasing the code size.

If you don't mind getting your hands dirty with some serious Math, there are crazy number-theory methods like the Miller-Rabin test. Note that, using the right set of witnesses, these methods are provably correct for all numbers within a reasonable range (see "Deterministic variants of the test").

  • Many of the fancier tests will have a tiny to small margin of error but I believe Miller-Rabin was rather good in that it is pretty much bullet-proof against pseudo-primes and Carmichael numbers. So if accuracy is important, I think Miller-Rabin would be a pretty good bet. – Priidu Neemre Dec 16 '12 at 20:52
  • 1
    As I noted, given the right witnesses, Miller-Rabin is error-free within a known range. For instance, testing with witnesses 2, 7, and 61 is sufficient for all 32-bit integers. It only becomes probabilistic if you're using randomized witnesses on large numbers. –  Dec 16 '12 at 20:55
  • Maybe I'm missing something, but won't the above implementation take `number % (0 + 1)`, get 0, and return composite right out of the gate? – Platinum Azure Dec 16 '12 at 21:00
  • Whoops - special cases strike again. Start the wheel at 6, not zero. –  Dec 16 '12 at 21:21
1
BigInteger.valueOf(x).isProbablePrime(50)

That'll probably be quite fast, assuming you're willing to tolerate a 1/1000000000000000 chance of error.

Louis Wasserman
  • 191,574
  • 25
  • 345
  • 413
0

Have a look at Sieve of Eratosthenes http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

user1888014
  • 157
  • 3