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
coding_geek1: 2021-09-23 19:12:26

Those who are still getting TLE using the below mentioned constraints try using fastio

mdminhaz: 2021-08-06 20:38:35

bool is_prime[90000001];
ll maxN = 90000001;
then do rest...

vikassnwl: 2021-08-01 19:38:38

n = 86028121
This is the accurate value to generate 5 million prime numbers.

toocurious: 2021-08-01 18:12:04

For those who are getting TLE with c++. Try using bool array instead of int array in sieve.

akshat_19: 2021-05-14 11:42:41

Codechef compiler showed 1.76 sec on given test cases yet I got AC.

rajkarmakar97: 2021-02-26 08:49:10

TLE .......why?

amitroy3370: 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

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

use array of size 90000001 with type bool

Last edit: 2020-12-20 07:02:18

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