WAP to Calculate nth Prime Number Efficiently

java program

class nth
{

public static void main(String a[])
{
nthfindPrime(5);
}
static void nthfindPrime(int n)
{
int i=0,count=2;
if(n==1)
{
System.out.println("1st prime =2");
return;
}
if(n==2)
{
System.out.println("2nd prime =3");
return;
}

while(true)
{
for(int j=2;j<=i/2;j++)
{
if(i%j==0)
break;
else if(j==i/2)
{
count++;
}
}
if(count==n)
{
System.out.println(n+"th prime ="+i);
break;
}
i++;
}
}
}

Time Complexity O(n)
Space Complexity O(1)

Run Here https://ideone.com/OHmO9


A More Efficient Version

#include
#include
using namespace std;

int main()
{
int i=0,count=2;int n=60;
if(n==1)
{
cout << "1st Prime Number = 2\n";
return 1;
}
if(n==2)
{
cout << "2nd Prime Number = 3\n";
return 2;
}
i=5;
float root2 = sqrt(2);
int limit;
while(true)
{
limit = (int)(i/root2);
for(int j=2;j<=limit;j++)
{
if(i%j==0)
break;
else if(j==i/2)
{
count++;
}
}
if(count==n)
{
cout << n << "th Prime No. : " << i << endl;
break;
}
i++;
}
}

http://en.wikipedia.org/wiki/Prime_number_theorem#Approximations_for_the_nth_prime_number

But number of Instruction Reduced
Time Complexity O(n)
Space Complexity O(1)
Run Here https://ideone.com/ncfzh