| Submit | All submissions | Best solutions | Back to list |
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
| 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 |
hide comments
|
|||||
|
2022-11-01 15:34:27
<snip> what's going wrong ??? runtime why??? [Simes]: use the forum for this. Last edit: 2022-11-02 09:04:09 |
|||||
|
2021-11-09 21:01:27
Segmented sieve + wheel gives me TLE ... Any solutions ? |
|||||
|
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? Update on 2021.7.18 Thanks for Mario's help! I finally solved the problem with it! Last edit: 2021-07-18 09:24:53 |
|||||
|
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? p.s. i am not storing all primes... just the ones that are asked in the query. |
|||||
|
2020-09-29 21:02:21
Are we getting 1.4 seconds? I get TLE immediately after compilation. [NG]: There was an AC just 5 days ago. Server web display may lag while your code TLEs. Solved! Last edit: 2020-10-01 17:34:15 |
|||||
|
2020-07-20 09:41:22
50000000 th prime is 982,451,653. |
|||||
|
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. |
|||||
|
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. Can anyone tell me how to fix this, here is my code..... [Do not post any source code here] Last edit: 2017-02-22 11:28:40 |
|||||
|
2016-07-16 16:25:52 ASHUTOSH DWIVEDI
As expected,getting TLE using segmented sieve is any other algo required |
|||||
|
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? is time 1.3sec for all queries? or per single query? Also what is the difference between this and TDKPRIME problem, except constraints? Last edit: 2016-03-28 09:58:06 |
|||||
RSS