Popular Posts

Wednesday, February 15, 2012

Nth prime number

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.

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