N'th Prime - Easy Problems - Solution to Toph.co Online Judge Problem

N'th Prime

Limits 1s, 512 MB

In this problem, you will have to print the n^th prime number. The first few prime numbers are given below:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, …

2 is the 1st prime, 3 is the 2nd prime, 5 is the 3rd prime, …

Input

The input will contain a single integer n (0 < n < 500000).

Output

Print the n^th prime number.

Samples

Input	Output
1	2

Input	Output
2	3

Solution:

#include <iostream> using namespace std; #include <iostream> using namespace std; int isPrime(int n) { if(n<=1) return false; if(n<=3) return true; if(n%2==0 || n%3==0) return false; // Main Code for(int i=5; i*i<=n; i+=6) { if(n%i==0 || n%(i+2)==0) return false; } return true; } int main() { int n; cin>>n; int i=2,c=0; while(1) { if(isPrime(i)==true) c++; if(c==n) { cout<<i<<endl; break; } i++; } return 0; }