# Calculating the nth prime number for huge BigIntegers

I wrote this simple class for calculating the nth prime:

package generator;

import java.math.BigInteger;

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
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
if (isPrime(candidate)) {
}
}
}

/*
* 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;
}
for (BigInteger i = SIX; i.compareTo(sqrtCandidate) <= 0; i = i
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;
while (b.compareTo(a) >= 0) {
if (mid.multiply(mid).compareTo(n) > 0) {
b = mid.subtract(ONE);
} else {
}
}
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?

• That's the problem with big primes; they're hard to calculate. Maybe you could add more patterns beside 6? I don't know. Java isn't that fast anyway.
– Blue
Oct 6, 2015 at 1:47

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.

• Thanks, I will apply your hints. I didn't use isProbablePrime, because it's not always correct, and for my application a wrong prime can make all the difference. Oct 25, 2015 at 9:04
• isProbablePrime will tell you very quickly if number if composite. So you don't need to do iteration in your loop in most cases. And you fallback to the loop if isProbablePrime returns false. Oct 25, 2015 at 11:07
• Oh, ok, so IsProbablePrime will only return "false" falsely, but never return "true" falsely? Oct 25, 2015 at 14:05
• That's right - and this gives you chance to optimize a program at least a little bit. Oct 25, 2015 at 18:43
• Sure, you should probably also ask on algorithms SO site for specific algorithms which may be more efficient as this is not software review problem but more research and algorithm problem Oct 26, 2015 at 8:38