3
\$\begingroup\$

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?
\$\endgroup\$
2
\$\begingroup\$

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");
\$\endgroup\$
2
\$\begingroup\$
        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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Mine ran in 14 milliseconds though... \$\endgroup\$ – TheCoffeeCup Jan 23 '15 at 20:22
  • 2
    \$\begingroup\$ @MannyMeng if you add that to how long it took to write ... ;) \$\endgroup\$ – Peter Lawrey Jan 24 '15 at 21:32

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.