SPOJ.com - Problem NTHPRIME

NTHPRIME - Nth Prime

There is no tedious description for this problem. You are just required to calculate and output the Nth prime number.

Input

The input consists of a single line containing an integer N, N ≤ 10^9.

Output

For each input file, output the Nth prime number.

Example

Input:
4

Output:
7

Note

The source limit is enabled to 4000B in order to restrict and discourage sending solutions with pre-computed tables.

Submit solution!

hide comments



	asutoshgha: 2020-09-13 09:04:30 any hints sieve is not working -> see the tags maybe? Last edit: 2020-11-06 22:28:23
	nimphy: 2018-05-02 10:44:13 @[Lakshman] : 跪求your help!
	mzuenni: 2018-03-31 23:02:46 @sgtlaugh can you look at my solution and tell me where it is wrong? (either my binary search or pi implementation is wrong but i cant find a counter example...) -> @mzuenni, sorry for a late response, but I just saw this. Seems you already got accepted :) Last edit: 2018-10-13 16:12:50
	Sushant Moon: 2017-10-05 11:00:21 @[Lakshman] : can you give any hints on how you proceeded with this problem. Any general direction would be very much appreciated. Last edit: 2017-10-05 11:00:33
	[Lakshman]: 2017-07-09 16:49:21 @sgtlaugh I think my approach is correct, but getting WA. Can you Please see why I am getting WA. My bad got AC. Last edit: 2017-07-09 18:30:45
	ar7ab: 2015-09-05 12:19:32 my code is giving the perfect output in IdeOne but it's not getting accepted in here -> The input is correct. It's not getting accepted because your program doesn't output correct answer for most cases. Please check your program again. Last edit: 2015-09-07 06:39:12
	raghulvirus: 2015-09-01 08:02:17 hi
	Francky: 2015-08-25 18:45:46 Moved to tutorial ; this one don't give very new stuff to do. -> I haven't solved something similar in SPOJ. Can you mention something similar? The intended solution is much different than that of KPRIMES2. =(Francky)=> I thought at http://www.spoj.com/problems/SUMPRIM2/ (very similar), but if you confirm that KPRIMES2 isn't enough, then we can consider to put your problem back to classical, it would be an intermediate difficulty one. Sorry if I didn't check with a basic solution. Moved back, as there are very few solver for SUMPRIM2. Last edit: 2015-08-25 21:17:20

Submit solution!

Added by:	sgtlaugh
Date:	2015-08-25
Time limit:	2.667s
Source limit:	4000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: GOSU
Resource:	Own Problem