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:
- This obviously is not efficient. How can I improve it?
- Are there any bad practices?