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
princemishra: 2020-10-15 11:53:51

learn sieve of erathosthenes

eagle_2002: 2020-09-30 10:59:10

how to reduce time limit i got it 1.11 second in c++

singhsaab_056: 2020-09-13 21:28:43

C++ implementation gives a TLE with Memory of 731 mb using array of size 87000009.

disha_s1ingh: 2020-09-13 07:47:44

not getting why my solution failed using Java, help please!

rrb_ragini99: 2020-09-10 20:32:20

do the queries need to be in ascending order?

vsinghal69: 2020-07-07 06:30:21

just run the seive code only once(before reading t) and make global bool array..

sajin_amin02: 2020-06-24 12:03:59

used vector bool to declare and initialize in one line, got AC in the first go, feeling good with efficient code

acktron: 2020-06-23 09:50:14

Solved in one go....
using bool array in c++.

dishantsheth: 2020-06-17 18:08:57

In Java, any implementation other than a bit-wise sieve will give you a TLE.

dv_kil: 2020-06-13 11:52:14

How can I implement this using python?


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 qobi SCM guile ST SQLITE TCL WHITESPACE
Resource:Thanks to TDuke