Created an array to hold all the discovered primes. For a given a number, check if it already is in the list or not. If yes, it is a prime. If not, check if any of the primes in the list, less than square root of the number, is a factor of this number or not.
The solution proposed by the Project Euler authors improvised on this. They used an additional fact that any prime greater than 3 is of the form 6k+/-1.
If you know the upper bound of the prime number, then the Sieve of Eratosthenes gives the answer much quickly.
The solution proposed by the Project Euler authors improvised on this. They used an additional fact that any prime greater than 3 is of the form 6k+/-1.
If you know the upper bound of the prime number, then the Sieve of Eratosthenes gives the answer much quickly.
import java.util.ArrayList;
import java.util.List;
public class NthPrimeNumber {
public static void main(String[] args) {
int index = 5;
if (index == 1) {
System.out.println(2L);
return;
}
// An array of all the discovered primes
List<Long> primes = new ArrayList<Long>();
primes.add(2L);
Long num = 3L;
// Search for primes by dividing num with all the known prime numbers
while (primes.size() != index) {
boolean isComposite = false;
double sqrt = Math.sqrt(num);
for (Long p : primes) {
if (p > sqrt)
break;
if (num % p == 0) {
isComposite = true;
break;
}
}
if (!isComposite)
primes.add(num);
num++;
}
System.out.println(primes.get(index - 1));
}
}
No comments:
Post a Comment