Project Euler : Find the nth Prime | Diabolical or Smart | Anuvrat Singh

Project Euler : Find the nth Prime | Diabolical or Smart | Anuvrat Singh

The seventh problem in Project Euler is stated thus:

Find the 10001st prime number.

public Long getPrimeByIndex(int index) {
if (index == 1)
return 2L;

// An array of all the discovered primes
List primes = new ArrayList();
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);
}

If we can't use extra space:
http://javabrowsers.blogspot.com/2012/05/finding-nth-prime-number.html
public static void main(String[] args) {
Scanner console = new Scanner(System.in);
System.out.println("enter the nth prime number to find: ");
int nthPrime = console.nextInt();
int prime = 0;
if(nthPrime<=0)
{
System.out.println("Wrong Input");
}
else
if(nthPrime==1)
{
System.out.println("Prime value "+2);
}else
if(nthPrime==2)
{
System.out.println("Prime value "+3);
}else
{
int number = 3;//last prime value i tested
prime = 2;//identified the first 2 primes.
// continue testing until prime == nth prime
while(prime<nthPrime)
{
boolean isFlag = true;
number+=2;
                                                int sqrt = Math.sqrt(number);
                                     
for(int i = 3;i<=sqrt;i++)
{
                                                     //isFlag Becomes false only if the number is odd number and not prime.
if(number%i==0)
{
isFlag = false;

}

}
                                          //prime value increments if and only if number is prime number
if(isFlag==true)
{
prime += 1;
}

}
System.out.println("Prime value "+number);
}

}
http://javablogx.blogspot.com/2014/09/calculating-and-printing-nth-prime.html
Read full article from Project Euler : Find the nth Prime | Diabolical or Smart | Anuvrat Singh