TDKPRIME - Finding the Kth Prime


The problem statement is really simple. There are some queries. You are to give the answers.

Input

An integer stating the number of queries Q(equal to 50000), and Q lines follow, each containing one integer K between 1 and 5000000 inclusive.

Output

Q lines with the answer of each query: the Kth prime number.

Example

Input:
7
1
10
100
1000
10000
100000
1000000

Output:
2
29
541
7919
104729
1299709
15485863

hide comments
harsh123_: 2017-01-25 05:28:13

Use Segmented Sieve...Took only 3.4MB space
But how to make it time efficient..It took 0.67 sec

Last edit: 2017-01-25 05:28:55
madhavgaba: 2017-01-15 19:01:58

how can the top solution be 3.4M and 0.04 sec!!!!

vivace: 2016-12-22 23:04:16

also , how is the memory use just 3.6 MB for best AC solution as per time limit.. sieve+an array till required takes 22MB in my case

vivace: 2016-12-22 23:02:54

how are people getting 0.04 seconds while my nloglogn sieve of eratosthenes, several loop counter modifications alongwith scanf and printf got 0.56?

iharsh234: 2016-07-08 11:44:04

do it just for bitwise seive.
cool problem
bitwise seive - > 0.45 sec
linear seive -> 0.75 sec

Last edit: 2016-07-08 11:59:28
blueranger: 2016-06-15 20:07:19

@Alfonso2 Peterssen Last submitted solution is working perfectly on my machine. Can you please tell me why am I getting WA?

surya2196: 2016-04-05 19:12:44

lolypop question

Sriharshaa Sammeta: 2015-09-03 12:32:42

can u please give explanation or some sort of idea about bitwise sieve ?

SangKuan: 2015-07-18 18:07:12

in debug mode i use 2~3 second,but only use 0.77s in spoj,haha

:.Mohib.:: 2015-07-06 22:29:28

Nice One :)

Last edit: 2015-07-06 22:30:54

Added by:Alfonso2 Peterssen
Date:2010-04-06
Time limit:1.240s
Source limit:10000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM32 ASM64 BF CLPS LISP clisp LISP sbcl ERL HASK ICON ICK JS-RHINO LUA NEM NICE OBJC OCAML PHP PIKE PRLG-swi SCALA SCM guile SCM qobi ST SQLITE TCL WHITESPACE
Resource:Thanks to TDuke