4
\$\begingroup\$

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?

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Blue Oct 6 '15 at 1:47
1
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Andreas Hartmann Oct 25 '15 at 9:04
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Maxim Galushka Oct 25 '15 at 11:07
  • 1
    \$\begingroup\$ Oh, ok, so IsProbablePrime will only return "false" falsely, but never return "true" falsely? \$\endgroup\$ – Andreas Hartmann Oct 25 '15 at 14:05
  • 1
    \$\begingroup\$ That's right - and this gives you chance to optimize a program at least a little bit. \$\endgroup\$ – Maxim Galushka Oct 25 '15 at 18:43
  • 1
    \$\begingroup\$ 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 \$\endgroup\$ – Maxim Galushka Oct 26 '15 at 8:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.