8

I am writing a method that detects if a BigInteger is prime or not. I have used the following code/algorithm to check if a given number is prime or not. But this is extremely slow and takes long time if a number is lets say 10 digits long. 

 public boolean returnPrime(BigInteger testNumber){
        int divisorCounter=1;
        BigInteger index,i ;


        for ( index= new BigInteger("2"); index.compareTo(testNumber) !=1; index=index.add(new BigInteger("1"))){


            System.out.println(index);
            for(i= new BigInteger("2"); i.compareTo(index) != 1; i=i.add(new BigInteger("1"))){
            if((testNumber.mod(i).equals(BigInteger.ZERO) )){
            divisorCounter++;

            }

            if(divisorCounter>2){
            return false;
            }

            }       

        } 
    return true;

    }

Is there any better algorithms to work with BigInteger prime number? I could not find a question related to this in Stackoverflow. If you have came across such question please let me know or if you have an idea on how to solve then your ideas are much appreciated.

Ram
  • 93
  • 1
  • 1
  • 4

3 Answers3

12

Here's an optimized version using testing only up to sqrt(n) and using the Miller-Rabin test (as of Joni's answer):

public boolean returnPrime(BigInteger number) {
    //check via BigInteger.isProbablePrime(certainty)
    if (!number.isProbablePrime(5))
        return false;

    //check if even
    BigInteger two = new BigInteger("2");
    if (!two.equals(number) && BigInteger.ZERO.equals(number.mod(two)))
        return false;

    //find divisor if any from 3 to 'number'
    for (BigInteger i = new BigInteger("3"); i.multiply(i).compareTo(number) < 1; i = i.add(two)) { //start from 3, 5, etc. the odd number, and look for a divisor if any
        if (BigInteger.ZERO.equals(number.mod(i))) //check if 'i' is divisor of 'number'
            return false;
    }
    return true;
}
Nam G VU
  • 33,193
  • 69
  • 233
  • 372
Juan Lopes
  • 10,143
  • 2
  • 25
  • 44
  • Well I tested your code and I have to say its clean and much simpler! Thank you! – Ram Aug 16 '15 at 15:50
  • Hi @Juan Lopes, what is the reason for incrementing "i" by "two" instead of just a single step? – sunsin1985 Mar 21 '17 at 18:52
  • @sunsin1985 Because we are testing for divisibility by two earlier, so we don't have to test for divisibility by even factors. In a most optimized version, we would only test prime factors. But that would require computing and storing up to sqrt(n) primes in memory. However, testing if the number is even earlier allows us to cut the number of divisions by half, so it is worth the optimization. – Juan Lopes Mar 22 '17 at 18:27
  • 1
    This code makes no sense at all. You're using `isProbablePrime` with a very low level of certainty, and then doing a regular brute force sieve that doesn't stop at sqrt(N), it goes all the way up to N. Why not just use `isProbablyPrime` with a high level of certainty? It would be much faster. – Jason S Sep 21 '18 at 17:42
  • 1
    @JasonS It uses `isProbablePrime` just as a probabilistic optimization step. Miller-Rabin probability test is fast and exact when the answer is negative. You would only have to check when it returns `true`, meaning it is probably prime. Also, it does stop at sqrt(N), checking whether `i*i <= N` does that without having to compute the square root explicitly. – Juan Lopes Sep 23 '18 at 21:40
  • 1
    oh, I did miss that second part, for some reason, sorry; for some reason I read `i.compareTo(number) < 1)`. But you're still only using Miller-Rabin with confidence level 1 - (1/4)^5 = 90.2%. That's awful; it's a fast test so you really ought to increase the `5` to something higher like 20 or 30. Also, for what it's worth, calculating sqrt(N) once is much quicker than computing `i.multiply(i)` repeatedly. There are ways to reduce the number of multiply operations that are faster than both. – Jason S Sep 26 '18 at 03:18
  • You don't need to check every uneven number up to the root, you could use i = i.nextProbablePrime(), it could falsely increase i to a number which is not a prime, but it can't skip a prime by falsely stepping over it. A bit more complicated way would be by using some primorial base, if you use the base 30 for example, you have only to check 8 of 30 numbers for primality instead of 15 of 30 if you would check every odd number. The bigger base you use, the less numbers you have to check. Using base 210 you only need to check 48 of 210, base 2310 only 480 out of every 2310 numbers, and so on. – Eugen Feb 13 '20 at 02:14
5

Check if the integer is a "probable prime." If it's not you know for sure that it's composite and you avoid the slow factorization.

if (!testNumber.isProbablePrime(5)) return false;

Also you only need to make trial divisions only up to the square root of testNumber. If K is composite you know that its least prime factor must be at most sqrt(K).

Joni
  • 108,737
  • 14
  • 143
  • 193
0

Some other simple improvements would be to limit your set of possible numbers to only two and odd numbers in your outer loop and also to only iterate up to the square root of "index" (or index / 2 if too hard to calculate) in your inner loop.

Brendan Rollinson
  • 204
  • 1
  • 6