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?