NPRIME - Nth Prime


Given an integer 1 <= N <= 100000, you have to print the Nth prime number.

Score is the length of your source.

Input

The input file consists of series of numbers one in each line.The input is terminated by EOF.

Output

The Nth prime number.

Example

Input: 
3
5
7
11

Output:

5
11
17
31

PS: Timit limit and test cases are modified on 05.10.2010 to encourage more short solution.

hide comments
ankit: 2013-08-16 09:33:43

easy... just apply sieve

Prayank Mathur: 2013-08-04 18:11:03

does erastosthenes work ??..
mine giving tle..

EDIT-->did some optimization...finally AC !!

Last edit: 2013-08-05 16:00:38
mystique_blue: 2013-06-15 16:42:53

Yuuuuhoooo. Seems as if I have conquered the world. Though I am not among the best but still I am over satisfied with myself right now... :D

Last edit: 2013-06-15 16:43:52
Mitch Schwartz: 2013-05-17 21:44:09

The real top score is 86 in Perl by Jander at http://www.spoj.com/SHORTEN/ranks/NPRIME/ .

Shashi Kant Prasad: 2013-04-21 07:57:06

Last edit: 2014-01-26 11:57:10
shaik azhar madar: 2013-03-09 04:44:04

eof?
--ans--> EOF

Last edit: 2013-03-09 08:46:48
Aditya Pande: 2012-06-20 13:24:24

AC algo in C gives TLE in RUBY
Edit: finally got it in a slow language like RUBY

Last edit: 2012-10-24 10:02:48

Added by::(){ :|: & };:
Date:2010-10-04
Time limit:2s-4.5s
Source limit:256B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64