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
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
prateek7248: 2022-08-29 13:07:33

how can we solve it in 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 guile SCM qobi ST SQLITE TCL WHITESPACE
Resource:Thanks to TDuke