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
arifin_abir: 2024-11-17 14:39:09

how you guys are think that n=90million?

onday: 2024-11-07 15:36:30

please use n = 86028122 else you will face problem with bool also

hridoymia001: 2023-10-23 12:52:05

sieve of erastothenes code gives time limit

rik_01_11: 2023-10-07 00:16:56

having trouble see this explanation https://www.youtube.com/watch?v=-DHwP-oAV_0&list=PLN4aKSfpk8TQDJz7KLiwGFgnoUUwzfl1i&index=3&t=688s

arjunac_7: 2023-09-26 15:35:59

can anyone share the solution in java!!???

pseudofool: 2023-03-04 10:25:19

For those who are asking how to find that there are 5 million primes under 90 million:
" The number of prime numbers less than or equal to  n is approximately  n / ln(n) "
For more info check this "https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html#implementation"

iangkur: 2023-01-15 12:38:35

How do you guys know that there are 5 million primes under 90 million? I mean, is there any equation?

shelby_sravan: 2022-12-31 12:03:58

If any one have python code please share it

ayush_7901: 2022-12-20 10:40:54

Used sieve of erastothenes solved in 1 go

kodershut: 2022-11-29 19:00:37

how to guess the value of n, like under which we can generate 5million primes.

Last edit: 2022-11-30 05:37:38

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