Calculating the nth prime number for huge BigIntegers

Question

I wrote this simple class for calculating the nth prime:

package generator;

import java.math.BigInteger;

public class SimplePrimeNumberGenerator implements PrimeNumberGenerator {

    private static final BigInteger MINUS_ONE = BigInteger.valueOf(-1);
    private static final BigInteger ZERO = BigInteger.ZERO;
    private static final BigInteger ONE = BigInteger.ONE;
    private static final BigInteger TWO = BigInteger.valueOf(2);
    private static final BigInteger THREE = BigInteger.valueOf(3);
    private static final BigInteger SIX = BigInteger.valueOf(6);
    private static final BigInteger EIGHT = BigInteger.valueOf(8);

    @Override
    public BigInteger calculateNthPrimeNumber(BigInteger n) {
        if (n.compareTo(ZERO) <= 0) {
            throw new NumberFormatException(
                    "Can not calculate nth prime number for n=" + n);
        }
        BigInteger candidate, count;
        for (candidate = TWO, count = ZERO; count.compareTo(n) == -1; candidate = candidate
                .add(ONE)) {
            if (isPrime(candidate)) {
                count = count.add(ONE);
            }
        }
        return candidate.add(MINUS_ONE);
    }

    /*
     * Performs a simple primality test on the input parameter.
     */
    private static boolean isPrime(BigInteger candidate) {

        if (candidate.isProbablePrime(2)) {
            if (candidate.compareTo(TWO) == -1) {
                return false;
            }
            if (candidate.equals(TWO) || candidate.equals(THREE)) {
                return true;
            }
            if (candidate.mod(TWO).equals(ZERO)
                    || candidate.mod(THREE).equals(ZERO)) {
                return false;
            }
            BigInteger sqrtCandidate = sqrt(candidate).add(ONE);
            for (BigInteger i = SIX; i.compareTo(sqrtCandidate) <= 0; i = i
                    .add(SIX)) {
                if (candidate.mod(i.add(MINUS_ONE)).equals(ZERO)
                        || candidate.mod(i.add(ONE)).equals(ZERO)) {
                    return false;
                }
            }
            return true;
        } else {
            return false;
        }
    }

    /*
     * Derived from:
     * http://faruk.akgul.org/blog/javas-missing-algorithm-biginteger-sqrt/
     */
    private static BigInteger sqrt(BigInteger n) {
        BigInteger a = ONE;
        BigInteger b = n.shiftRight(5).add(EIGHT);
        while (b.compareTo(a) >= 0) {
            BigInteger mid = new BigInteger(a.add(b).shiftRight(1).toString());
            if (mid.multiply(mid).compareTo(n) > 0) {
                b = mid.subtract(ONE);
            } else {
                a = mid.add(ONE);
            }
        }
        return a.subtract(ONE);
    }
}

It scales reasonably well for five-digit-numbers n, but I need really large prime numbers (which is why I went with BigInteger in the first place). How can I achieve reasonable performance (one prime in less than five seconds) for calculating, say, the 10.000.000.000th prime number?

Answer 1

Small nit:

if (candidate.compareTo(TWO) == -1)
    return false;

This is implementation dependence on BigInteger - better to use generic way:

if (candidate.compareTo(TWO) < 0) {
    return false;
}

Also - this is in general more readable and less error-prone to wrap the if statements in {}-brackets even for 1-liners.

Some tricks to possibly improve performance:

• Precalculate Erathosphenes sieve till some number you can handle sieve completely in memory (don't use BigInteger for storing those) and check up to sqrt but iterating through primes only and when you exhausted sieve - switch back to your method.

• Did you try BigInteger#isProbablePrime here? This will tell you much faster if current number is composite - so you will do less checks.