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
abhinandan824: 2020-04-25 10:30:15

@sanket17
how did you came with that number 87 million?

abhinandan824: 2020-04-25 10:29:20

@loser_404
Because bool is just one bit and integer is 4 bits

loser_404: 2020-04-09 14:11:55

why using bool array gets accepted?rather than using vector<long long>? can any one explain?

rockingcoder97: 2020-01-30 19:54:20

getting a runtime error

sanket17: 2020-01-22 11:02:52

Apply sieve till 87000008
and instead of bool array use bitset

aryan29: 2019-10-14 14:15:43

precalculate all and submit 0.04 sec thats it

akashbhalotia: 2019-05-22 19:53:11

In Java, I had to use Fast IO, and bitwise sieve+bitset to get AC.

maxboom321: 2018-09-19 18:01:03

Took 0.76 sec using bitwise_seive.How to improve?

eagleshadow: 2018-09-08 16:58:10

used bitwise sieve
0.24 s
21M
how can i imporve my solution?

himanshu_159: 2018-01-14 07:29:58

@ayushgupta1997 how you got the max value


Added by:Alfonso² 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 sbcl LISP clisp 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