Prime number util class

A prime number util, which provides 3 APIs - find the nth prime, find the next prime, and find all primes up to n.

I must admit this code has been influenced a lot by discussions here. I'm looking for code review, optimizations and best practices.

```
public final class PrimeUtil {

private static final boolean COMPOSITE = true;
private static final int DEFAULT_SIZE = 100;

// cache of primes.
public final List primes;
public int cachedMaxPrime;

public PrimeUtil() {
primes = new ArrayList();
// initial seed
primes.addAll(Arrays.asList(2, 3, 5, 7, 11, 13));
cachedMaxPrime = primes.get(primes.size() - 1);
}

private void validatePositive(int n) {
if (n getPrimesUptoN(int n) {
validatePositive(n);
validateOutOfBound(n);

if (n list = new ArrayList();
for (int i = 0; primes.get(i) computePrimesUptoN(int n) {
// composite is name of the sieve, ie nothing else but the sieve.
// optimizing the sieve size, but trimming it to "n - cacheprime"
boolean[] composites = new boolean[n - cachedMaxPrime];
int root = (int)Math.sqrt(n);

// loop through all "first prime upto max-cached-primes"

/*
* We need i primes = Arrays.asList(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47);
Assert.assertEquals(primes, primeUtil.getPrimesUptoN(50));

primes = Arrays.asList(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97);
Assert.assertEquals(primes, primeUtil.getPrimesUptoN(100));

Assert.assertEquals(2, primeUtil.getNthPrime(1));
Assert.assertEquals(3, primeUtil.getNextPrime(2));

Assert.assertEquals(13, primeUtil.getNthPrime(6));
Assert.assertEquals(17, primeUtil.getNextPrime(13));

Assert.assertEquals(281, primeUtil.getNthPrime(60));
Assert.assertEquals(283, primeUtil.getNextPrime(281));
}
}

The code seems pretty good. I just have a few eclectic comments.

Consider making the class a singleton so that computations can be shared. There may be lock contention issues, though.

Input Validation

• getNextPrime() could be more lenient: why require the parameter to be prime itself? It seems reasonable to ask, "What is the next prime after 14?" Also, why require the input to be positive? The next prime after -50 is 2.

• validatePositive() and validateOutOfBound() do essentially the same thing, with a slightly different error message. In getPrimesUptoN(), you call both validators. Obviously, the second call is just wasted.

• Why not move the overflow check into computePrimesUptoN() itself, instead of calling validateOutOfBound() all over the code?

• In my judgment, only getNthPrime() and computePrimesUptoN() need to check that they have positive parameters. At that point, you might as well get rid of the validation helper and throw the exception directly. It would also result in a less weird stack trace, since the function that throws the IllegalArgumentException is the one that actually has been passed the illegal argument.

Prime distribution theory

You expand the sieve 100 numbers at a time. I think we can do better.

• The nth prime should be approximately pn ≈ n ln(n). You can use that estimate in getNthPrime().

• What's the probable gap between successive prime numbers? The average gap is ln(p), so you could take that into consideration instead of blindly expanding by 100 at a time.

Expanding 100 at a time might have better overflow behaviour, though. I haven't thought that through.

computePrimesUptoN()

-
Your code doesn't match your comment:

// Try cache of {3, 5, 7}…
for (int i = 0; i < primes.size() && primes.get(i) <= root; i++) {
    …
}

You can start with i = 1, as there is no sense in striking out multiples of 2.

-
The way you arrive at firstPrimeMultiple is clumsy. This expression works:

// get the first odd multiple of this prime, greater than max-prime
int firstPrimeMultiple = prime * ((cachedMaxPrime / prime + 1) | 1);

The | 1 at the end rounds up to the next odd multiple.

Recommended tests

Nice that you have unit tests. I would add a few tests:

• Assert.assertEquals(Arrays.asList(), primeUtil.getPrimesUptoN(-5)); — to check for the more lenient validation

• Assert.assertEquals(17, primeUtil.getNextPrime(15)); — to check for the more lenient validation

• Assert.assertEquals(30529, primeUtil.getNextPrime(30526)); — to see what happens with a sudden large expansion of the sieve

Sample of changed functions:

public synchronized int getNthPrime(int n) {
    validatePositive(n); 

    // The nth prime should be approximately n ln(n).  Let's overestimate by 20%.
    assert primes.size() >= 5;
    for (int size = (int)(1.2 * n * Math.log(n)); primes.size() = primes.size()) {
        int size = Math.max(n, primes.get(primes.size() - 1));
        computePrimesUptoN(size + (int)(1.2 * Math.log(size)));
    }
    return primes.get((primeIndex  computePrimesUptoN(int n) {
    if (n <= 0) {
        throw new ArithmeticException("Arithmetic overflow");
    }

    // composite is name of the sieve, ie nothing else but the sieve.
    // optimizing the sieve size, but trimming it to "n - cacheprime"
    boolean[] composites = new boolean[n - cachedMaxPrime];
    int root = (int)Math.sqrt(n); 

    // loop through all "first prime upto max-cached-primes"

    /*
     * We need i <= root, and NOT i < root
     * Try cache of {3, 5, 7} and n of 50. you will really why
     */
    for (int i = 1; i < primes.size() && primes.get(i) <= root; i++) {
        int prime = primes.get(i);

        // get the first odd multiple of this prime, greater than max-prime
        int firstPrimeMultiple = prime * ((cachedMaxPrime / prime + 1) | 1);
        filterComposites(composites, prime, firstPrimeMultiple, n);
    }

    // loop through all primes in the range of max-cached-primes upto root.
    for (int prime = cachedMaxPrime + 2; prime < root; prime = prime + 2) {
        if (!composites[prime]) {
            // selecting all the prime numbers.
            filterComposites(composites, prime, prime, n);
        }
    }

    // by doing i + 2, we essentially skip all even numbers
    // also skip cachedMaxPrime, since quite understandably its already cached.
    for (int i = 1; i < composites.length; i = i + 2) {
        if (!composites[i]) {
            primes.add(i + cachedMaxPrime + 1);
        }
    }

    cachedMaxPrime = primes.get(primes.size() - 1);
    return primes;
}

StackExchange Code Review Q#44929, answer score: 3