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
|
aahad810:
2022-11-01 15:34:27
<snip>
|
|
karygauss03:
2021-11-09 21:01:27
Segmented sieve + wheel gives me TLE ... Any solutions ? |
|
leasier:
2021-04-09 16:03:11
I got TLE after using segmented sieve + Wheel Factorization of 2, 3, 5, 7, 11, 13, 17. Could someone please give me some optimization suggestions?
|
|
it_11199:
2020-10-07 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:
2020-09-29 21:02:21
Are we getting 1.4 seconds? I get TLE immediately after compilation.
|
|
sohelr360:
2020-07-20 09:41:22
50000000 th prime is 982,451,653. |
|
noble_mushtak:
2019-06-23 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:
2017-02-22 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:
2016-07-16 16:25:52
As expected,getting TLE using segmented sieve is any other algo required |
|
ash_hacker:
2016-03-28 09:32:32
My program takes 2-3 secs for pre-computing, then generates prime for n=50000000 in 32ms, and still they TLE? Can any admin check my submission?
|
| Added by: | Alfonso² Peterssen |
| Date: | 2010-04-09 |
| Time limit: | 1.399s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | C C++ 4.3.2 CPP JAVA PAS-GPC PAS-FPC |
| Resource: | Thanks to TDuke |
RSS