Prateek loves candy

#1

code : https://ide.codingblocks.com/s/206460

code is correct… still it showing TLE?

#2

When the number of test cases is less, your code is working fine.
The problem with your code is that for large number of test cases you are running the prime sieve again and again for each test case which is making the process inefficient and exceeding the time limit. So call the prime sieve function outside the loop for the test case.
Follow this approach:(I have commented out the steps)

Prateek loves candy
#3

as you told… i have taken the prime sieve function outside the loop

now four of the test cases are passing.
still one remaining

#4

Optimize it more by preventing the loop you have created in line 33. Refer the code i have shared for help.

#5

the reason i am insisting with my code is… the code you gave uses vector
and i dont have much idea about vector as of now.

can you correct my code by optimizing it?

#6

In place of vectors, you can use array. Maintain an array that will store only the primes.
Such that the 1st prime number be at 0th index
2nd prime number at 1st index and so on…So that within the loop for testcase, you can do lookup for nth prime in constant time.

#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#8

my doubt is still not clear… you explained me the step which i already did