The seventh problem in Project Euler is stated thus:
Find the 10001st prime number.
Well, there are two ways that I knew of to find the prime numbers. One is by checking if it has any factors below sqrt(n) and the second method is the Sieve of Eratosthenes. I checked online to search for a better method, but could not find any. So I decided to go ahead implementing the factor thing.
I created an array to hold all the discovered primes. Now given a number, I check if it already is in the list or not. If yes, it is a prime. If not, I check if any of the primes in the list, less than square root of the number, is a factor of this number or not. My code was able to all these computations and throw the answer in 94ms.
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.
Also, another thing that I read was that if you know the upper bound of the prime number, then the Sieve of Eratosthenes gives the answer much quickly. To estimate the upper bound Wikipedia has a topic called Prime Number Theorem, which could be looked up.
I am pasting below the piece of code I wrote to generate the 10001st prime number:
public class Problem_7 {
public Long getPrimeByIndex(int index) {
if (index == 1)
return 2L;
// An array of all the discovered primes
List<Long> primes = new ArrayList<Long>();
primes.add(2L);
Long num = 3L;
// Start the stopwatch
Stopwatch stopwatch = new Stopwatch();
stopwatch.start();
// 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++;
}
stopwatch.stop();
System.out.println("The reading for operation is: " + stopwatch);
return primes.get(index - 1);
}
public static void main(String[] args) {
System.out.println((new Problem_7()).getPrimeByIndex(10001));
}
}
Popularity: 24% [?]
Related posts:
