KPRIMES2  Finding the Kth Prime (Hard)
The problem statement is really simple (the constraints maybe not). There are some queries. You are to give the answers.
Input
An integer stating the number of queries Q(equal to 100000), and Q lines follow, each containing one integer K between 1 and 50000000 inclusive.
Output
Q lines with the answer of each query: the Kth prime number.
Example
Input: 8 1 10 100 1000 10000 100000 1000000 10000000 Output: 2 29 541 7919 104729 1299709 15485863 179424673
hide comments
it_11199:
20201007 18:56:34
Not able to figure out why am I getting tle after using segmented sieve + wheel of 2,3,5,7,11. Any optimization suggestions?


weathervane:
20200929 21:02:21
Are we getting 1.4 seconds? I get TLE immediately after compilation.


sohelr360:
20200720 09:41:22
50000000 th prime is 982,451,653. 

noble_mushtak:
20190623 16:03:50
This problem can be solved using bitset and segmented sieve+wheel factorization, but requires lots of optimization. Memory limit is over 1GB, but if you are reading/writing to more than 100MB, I think you will probably TLE. My solution ran in 1.38s and 11M. 

thinkwise:
20170222 10:53:35
Why i am getting run time error. My code runs perfectly in my computer even for the limit also but still i am getting run time.


ASHUTOSH DWIVEDI:
20160716 16:25:52
As expected,getting TLE using segmented sieve is any other algo required 

ash_hacker:
20160328 09:32:32
My program takes 23 secs for precomputing, then generates prime for n=50000000 in 32ms, and still they TLE? Can any admin check my submission?


pika_pika:
20131226 15:00:09
http://primes.utm.edu/nthprime/index.php#nth


triveni:
20121218 06:55:39
Anyone please reply what is the output for


kuszi:
20110128 18:39:12
@James Waldby Corrected 
Added by:  Alfonso² Peterssen 
Date:  20100409 
Time limit:  1.399s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  C C++ 4.3.2 CPP JAVA PASGPC PASFPC 
Resource:  Thanks to TDuke 