Project Euler #7 in Java

Question

Project Euler #7:

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?

Here is my solution:

public class PrimeFinder {

    public static void main(String[] args) {
        long time = System.nanoTime();
        int result = getNthPrime(10001);
        time = System.nanoTime() - time;
        System.out.println("Result: " + result
                + "\nTime used to calculate in nanoseconds: " + time);
    }
    
    private static int getNthPrime(int n) {
        int max = (int) (1.4 * n * Math.log(n));
        boolean[] isPrimeArray = new boolean[max + 1];
        for (int i = 2; i <= max; i++) {
            isPrimeArray[i] = true;
        }
        for (int i = 2; i * i <= max; i++) {
            if (isPrimeArray[i]) {
                for (int j = i; i * j <= max; j++) {
                    isPrimeArray[i * j] = false;
                }
            }
        }
        // Find the nth prime
        int nthPrime = 0;
        int index = 0;
        for(boolean isPrime : isPrimeArray) {
            if(isPrime) {
                nthPrime++;
            }
            if(nthPrime == n) {
                return index;
            }
            index++;
        }
        throw new IllegalArgumentException("n is not valid");
    }
}

It simply performs a sieve, and then find the 10001st true.

Output:

Result: 104743
Time used to calculate in nanoseconds: 13812289

Questions:

1. This obviously is not efficient. How can I improve it?
2. Are there any bad practices?

Answer 1

Instead of looping one more time through your isPrime array, consider expanding the iterations on your first for loop and then exiting from there once you reach the desired result:

    ...
    int counter = 0;
    for (int i = 2; i <= max; i++) {
        if (isPrimeArray[i]) {
            if (++counter == n) {
                return i;
            }
            for (int j = i; i * j <= max; j++) {
                isPrimeArray[i * j] = false;
            }
        }
    }
    throw new IllegalArgumentException("n is not valid");

Answer 2

        for (int i = 2; i * i <= max; i++) {

In my testing it's slightly faster to take the square root of max rather than multiplying i * i on each iteration.

        for (int i = 2, limit = 1 + (int)Math.sqrt(max); i <= limit; i++) {

It's only a fraction of a millisecond but a noticeable difference.

                for (int j = i; i * j <= max; j++) {
                    isPrimeArray[i * j] = false;
                }

You could simplify this.

                for (int j = i * i; j <= max; j += i) {
                    isPrime[j] = false;
                }

Then rather than doing two multiplications per iteration, you can do one addition. Of course a good optimizer would notice that both multiplications are the same and only do one.

I prefer names that do not include the type, so I'd just call it isPrime.

            if(isPrime) {
                nthPrime++;
            }
            if(nthPrime == n) {
                return index;
            }

You compare nthPrime and n more often than necessary. You can just say

            if (isPrime) {
                nthPrime++;

                if (nthPrime == n) {
                    return index;
                }
            }

As the result can only change when nthPrime does (or n but n never changes).

Incidentally, I tried expanding the for loop as @h.j.k. suggested but it ran more slowly than the original code. Only a fraction of a millisecond but slower.

Answer 3

It can be make much shorter which may be interesting and more efficient for the developer.

int prime = IntStream.range(2, Integer.MAX_VALUE)
        .filter(i -> IntStream.rangeClosed(2, (int) Math.sqrt(i))
                .noneMatch(n -> i % n == 0))
        .limit(10001).boxed()
        .collect(Collectors.reducing(null, (a, b) -> b));

This takes about a second to run.