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

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

hide comments
2021-05-14 11:42:41
Codechef compiler showed 1.76 sec on given test cases yet I got AC.
2021-02-26 08:49:10
TLE .......why?
2021-01-23 13:20:35
can I get some suggestion for solve this problem with java. I access the memory with 99000001.but it show's the run time error
2021-01-08 08:05:58
can we solve this using python,it is giving TLE,any idea for this

Last edit: 2021-01-08 08:06:28
2020-12-02 14:42:59
Can we solve the problem using python??

[NG]: Yes, but it's hard:
https://www.spoj.com/ranks/TDKPRIME/lang=PYTH%203.2.3
https://www.spoj.com/ranks/TDKPRIME/lang=PYTH%202.7

Try getting under 0.10s in PRIME1 first.

Last edit: 2020-12-03 02:15:53
2020-10-15 11:53:51
use array of size 90000001 with type bool

Last edit: 2020-12-20 07:02:18
2020-09-30 10:59:10
how to reduce time limit i got it 1.11 second in c++
2020-09-13 21:28:43
C++ implementation gives a TLE with Memory of 731 mb using array of size 87000009.
2020-09-13 07:47:44
not getting why my solution failed using Java, help please!
2020-09-10 20:32:20
do the queries need to be in ascending order?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.