2
\$\begingroup\$

Code review for best practices, optimizations, bug detection etc. Also please verify my complexity as mentioned within the function comments.

/**
 * Util class with 2 functions, 
 * 1. find the next consecutive prime 
 * 2. find the nth prime.
 */
public class PrimeUtil {

    private PrimeUtil() {}


    private static List<Integer> findAllPrimes(int upperBound) {
        assert upperBound > 0;

        final List<Integer> primeList = new ArrayList<Integer>();
        int squareRoot = (int) Math.sqrt(upperBound);

        boolean[] nonPrime = new boolean[upperBound + 1];

        for (int m = 2; m <= squareRoot; m++) {
            if (!nonPrime[m]) {
                primeList.add(m);
                for (int k = m * m; k <= upperBound; k += m)
                    nonPrime[k] = true;
            }
        }

        for (int m = squareRoot; m <= upperBound; m++) {
            if (!nonPrime[m]) {
                primeList.add(m);
            }
        }

        return primeList;
    }


    /**
     * Returns the next / consecutive prime number of input number.
     * 
     * Complexity: O (m * n) where m is number of primes till the input number, n is the difference between (to be found prime - input number)
     * 
     * @param number The number whose next prime should be returned
     * @return        The next / consecutive prime number of input prime.
     */
    public static int nextPrime (int number) {
        if (number <= 0) {
            throw new IllegalArgumentException("The value of n is " + number + ". It should be greater than 0");
        }

        int nextNum = number + 1;
        boolean notPrime = true;
        final List<Integer> primes = findAllPrimes(number);

        while (notPrime) {

            notPrime = false;
            for (int i : primes) {
                if (nextNum % i == 0) {
                    notPrime = true;
                }
            }
            if (notPrime) {
                nextNum++;
            } 
        }

        return nextNum;
    }


    /**
     * Returns the nth prime number.
     * 
     * Complexity: O(n * m) where n is the prime number, and m is number of primes till the n.
     * 
     * @param n     the nth prime number to be found.
     * @return      the nth prime number
     */
    public static int nthPrime(int n) {
        if (n <= 0) {
            throw new IllegalArgumentException("The value of n is " + n + ". It should be greater than 0");
        }

        final List<Integer> primes = new ArrayList<Integer>();
        int number = 2;

        while (primes.size() < n) {
            boolean notPrime = false;
            for (int i : primes) {
                if (number % i == 0) {
                    notPrime = true;
                }
            }
            // if you are a prime.
            if (!notPrime) {
                primes.add(number);
            }
            number++;
        }

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



    public static void main(String[] args) {
        System.out.println("Expected 101, Actual: " + nextPrime(100));
        System.out.println("Expected 17, Actual: " + nextPrime(15));

        System.out.println("Expected 7, Actual: " + nthPrime(4));
        System.out.println("Expected 29, Actual: " + nthPrime(10));
    }
}
\$\endgroup\$
  • \$\begingroup\$ How long does it take to calculate the 10 billionth prime? \$\endgroup\$ – gnasher729 May 13 '14 at 21:58
3
\$\begingroup\$

This question is very similar to the Project Euler #7 challenge. This was asked recently: Suggestions for improvement on Project Euler #7. I answered that question there, and a lot of my suggestions there will follow through here. I also suggested an object-oriented class that will significantly improve the performance of this problem....

Your solution is very different, but similar issues can be found...

Some basic 'hygiene':

  • double-negative logic is hard to read. if (!nonprime[m]) should be if (prime[m]). If you cannot get the booleab values to be right (Arrays.fill(prime, true)) then you should revert to constants (private static final boolean PRIME = false;) and == comparisons: if (primeflag[m] == PRIME)
  • you also do double-negative logic in the nextPrime() method: boolean notPrime = true; and if (notPrime). This should be something like if (!prime) ....

First though, you actually have two very different solutions for 'find nth prime' and 'find primes less than x'. Your find nth prime algorithm is very slow. It does not use the Sieve of Eratosthenes at all. It is a 'naive' and slow mechanism for checking every value against all primes. There is a way to estimate the value of the nth prime, and you should use that, combined with the mechanism for calculating primes less than the estimate. This is illustrated in that other answer (reference Wikipedia)

:

  1. you have blindly followed the wikipedia recommended algorithm/suggestion of doing an incremental progression on a sieve of numbers.
  2. if you make 2 a special case, then you only actually need to process every second value (m += 2 instead of m++).
  3. you do not cache previously computed prime numbers, as a result, calling your methods multiple times will require many re-computations of prime values.
  4. Integer.MAX_VALUE happens to be a prime.... what happens if you run: nextPrime(Integer.MAX_VALUE - 1); ?
\$\endgroup\$
  • \$\begingroup\$ Bug: If squareRoot happens to be a prime, it will be added twice. \$\endgroup\$ – gnasher729 Mar 23 '14 at 15:46
3
\$\begingroup\$

In addition to rolfl's suggestions:

A boolean occupies at least 1 byte on most VMs. You can reduce that by using a BitSet for your sieve. At least that should give you the ability to generate a sieve for all primes up to Integer.MAX_VALUE (2^28 entries vs 2^31 - the maximum number of elements in an array seems to be slightly below Integer.MAX_VALUE)

\$\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.