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.

• TheCoffeeCup: Mine ran in 14 milliseconds though...
• Peter Lawrey: @MannyMeng if you add that to how long it took to write ... ;)