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