TDKPRIME - Finding the Kth Prime
The problem statement is really simple. There are some queries. You are to give the answers.
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.
Q lines with the answer of each query: the Kth prime number.
Input: 7 1 10 100 1000 10000 100000 1000000 Output: 2 29 541 7919 104729 1299709 15485863
Took 0.76 sec using bitwise_seive.How to improve?
used bitwise sieve
@ayushgupta1997 how you got the max value
Simple Problem ,attempted after 1 year AC in one go :)
Is there some problem with the test cases, i checked/compared/double-checked the prime numbers generated by my sieve for first 5million primes, with 5million primes from https://primes.utm.edu/lists/small/millions/, they check out all of them are correct. But the test cases is giving me WA.
took 0.6 s...how to improve upon time
Use Segmented Sieve...Took only 3.4MB space
how can the top solution be 3.4M and 0.04 sec!!!!
also , how is the memory use just 3.6 MB for best AC solution as per time limit.. sieve+an array till required takes 22MB in my case
how are people getting 0.04 seconds while my nloglogn sieve of eratosthenes, several loop counter modifications alongwith scanf and printf got 0.56?
|Added by:||Alfonso2 Peterssen|
|Cluster:||Cube (Intel G860)|
|Languages:||All except: ASM32 ASM64 BF CLPS LISP clisp LISP sbcl 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|