5
\$\begingroup\$

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<Integer> primes;
    public int cachedMaxPrime;

    public PrimeUtil() {
        primes = new ArrayList<Integer>();
        // 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 <= 0) { 
            throw new IllegalArgumentException("Expecting a non-zero value");
        }
    } 

    private void validateOutOfBound(int n) {
        // resulted in int-overflow.
        if (n <= 0) {
            throw new IllegalArgumentException("The value is too large to calculate");
        }
    }


    /**
     * Find the nth prime. ie if n == 6, then return 13.
     * 
     * @param n     the nth prime  
     * @return      the prime at nth position
     */
    public synchronized int getNthPrime(int n) {
        validatePositive(n); 

        if (n <= primes.size()) {
            return primes.get(n - 1);
        }
        int size = cachedMaxPrime + DEFAULT_SIZE; // adding cachedMaxPrime to DEFAULT_SIZE is a tiny optimization, nothing else.
        while (primes.size() < n) {
            validateOutOfBound(size);
            computePrimesUptoN(size);
            size += DEFAULT_SIZE;
        }
        return primes.get(n - 1);
    }

    /**
     * Given an input prime, return the next prime.
     * ie, if prime == 13 then return 17, ie 17 is the next prime of 13.
     * 
     * @param prime     the prime number whose next should be found
     * @return          the next prime of the input prime.
     */
    public synchronized int getNextPrime(int prime) {
        validatePositive(prime); 

        int primeIndex = Collections.binarySearch(primes, prime);
        if (primeIndex != -1 && primeIndex != primes.size()) {
            return primes.get(primeIndex + 1);
        }
        int prevSize = primes.size();
        int size = cachedMaxPrime + DEFAULT_SIZE; // adding cachedMaxPrime to DEFAULT_SIZE is a tiny optimization, nothing else.
        while (primes.size() == prevSize) {
            validateOutOfBound(size);
            computePrimesUptoN(size);
            size += DEFAULT_SIZE;
        }
        return primes.get(primeIndex + 1);
    }

    /**
     * Given an input n, find all primes from 0 to n
     * Returns an unmodifiable list.
     * 
     * @param n     the number upto which the primes should be calculated
     * @return      An unmodifiable list.
     */
    public synchronized List<Integer> getPrimesUptoN(int n) {
        validatePositive(n); 
        validateOutOfBound(n);

        if (n < cachedMaxPrime) {
            List<Integer> list = new ArrayList<Integer>();
            for (int i = 0; primes.get(i) <= n; i++) {
                list.add(i);
            }
            return Collections.unmodifiableList(list);                
        }
        return Collections.unmodifiableList(computePrimesUptoN(n));
    }

    private List<Integer> 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 <= root, and NOT i < root
         * Try cache of {3, 5, 7} and n of 50. you will really why
         */
        for (int i = 0; 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 = (cachedMaxPrime + prime) -  ((cachedMaxPrime + prime) % prime);
            if (firstPrimeMultiple % 2 == 0) {
                /*
                 * since we know that no even number other than 2 can be a prime, we only want to consider odd numbers
                 * while filtering.
                 */
                firstPrimeMultiple += prime;
            }
            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;
    }

    private void filterComposites(boolean[] composites, int prime, int firstMultiple, int n) {
        // we want to add prime, twice to the multiple so that we only bother to filter odd-numbers.
        for (int multiple = firstMultiple; multiple < n; multiple += prime + prime) {
            // eg: assume n = 50, cachemax = 13, and multiple = 15, then 15 should be at composite position of 1.
            composites[multiple - cachedMaxPrime - 1] = COMPOSITE;
        } 
    }

    public static void main(String[] args) {
        PrimeUtil primeUtil = new PrimeUtil();

        List<Integer> 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));
    }
}
\$\endgroup\$
  • \$\begingroup\$ Nice question!! \$\endgroup\$ – rolfl Mar 21 '14 at 11:17
3
\$\begingroup\$

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.

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() < n; size = (int)(1.2 * size)) {
        computePrimesUptoN(size);
    }
    return primes.get(n - 1);
}

/**
 * Given an input number, return the next prime.
 * ie, if n == 13 or n == 14 then return 17.
 * 
 * @param n         the number whose next prime number should be found
 * @return          the next prime of the input.
 */
public synchronized int getNextPrime(int n) {
    if (n < 2) {
        return 2;
    }
    int primeIndex;
    while (Math.abs(primeIndex = Collections.binarySearch(primes, n)) >= primes.size()) {
        int size = Math.max(n, primes.get(primes.size() - 1));
        computePrimesUptoN(size + (int)(1.2 * Math.log(size)));
    }
    return primes.get((primeIndex < 0 ? ~primeIndex : primeIndex + 1));
}

private List<Integer> 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;
}
\$\endgroup\$
2
\$\begingroup\$
  1. You should indicate in the javadoc of the class that it's thread-safe.

  2. You should use a private lock object instead of synchronized methods:

    private final Object lock = new Object();
    ...
    public synchronized List<Integer> getPrimesUptoN(int n) {
        synchronized (lock) {
            validatePositive(n); 
            validateOutOfBound(n);
            ...
            return Collections.unmodifiableList(computePrimesUptoN(n));
        }
    }
    

    Consider the following code:

    final PrimeUtil primeUtil = new PrimeUtil();
    synchronized (primeUtil) {
    
    }
    

    Anyone can lock on this instance which could lead to poor performance or deadlock.

    See also: Effective Java 2nd Edition, Item 70: Document thread safety

  3. private static final int DEFAULT_SIZE = 100;
    

    I think DEFAULT_LOOK_AHEAD would be more descriptive. DEFAULT_SIZE is a little bit misleading.

  4. I'd rename the field to primeCache and remove the comment:

    // cache of primes.
    public final List<Integer> primes;
    

    See Clean Code by Robert C. Martin, Don’t Use a Comment When You Can Use a Function or a Variable, p67

  5. primes = new ArrayList<Integer>();
    

    You could save a line by putting this on the same line as the declaration:

    public final List<Integer> primes = new ArrayList<Integer>();
    

    I think it would be a little bit easier to follow.

  6. I'd put the validate methods at the end of the file. The are not so important to be the first methods.

  7. if (primeIndex != -1 && primeIndex != primes.size()) {
    

    I'd create a NOT_FOUND constant for -1 here for better readability.

\$\endgroup\$
  • \$\begingroup\$ Small issue with #2. There is no possible way for a deadlock with this class to occur. The class is entirely self contained. They only way there could be a deadlock is if a PrimeUtil instance relied on an another object that, in turn relied on that instance. \$\endgroup\$ – Brent Worden Mar 25 '14 at 21:05
2
\$\begingroup\$

In my previous answer, I missed two serious bugs, both in this loop in computePrimesUptoN():

// 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);
    }
}

The bugs are:

  • composites should be interpreted with an offset, such that composites[0] represents cachedMaxPrime + 1.
  • You should not mark prime itself as being composite.

That loop should be:

// 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 - cachedMaxPrime - 1]) {
        // selecting all the prime numbers.
        filterComposites(composites, prime, 3 * prime, n);
    }
}

The reason that your unit tests did not catch these bugs is that that codepath only gets exercised when the sieve is expanded to cachedMaxPrime2.

\$\endgroup\$

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.