Prateek Loves candy prob

#1

https://hack.codingblocks.com/contests/c/537/52
my code -https://ide.codingblocks.com/s/39673, how to improve this, so that it gives correct o/p?
i am using the sieve but am a lil stuck on how to print nth prime number using it

I have seen the reference-https://ide.codingblocks.com/s/13468
but here they already calculate sieve to a very large number and then whatever number is input by the user, sieve can be printed/used till then.

Isn’t there another way to do it, to calculate sieve only to the point/number we want?

Pls help.
thanks

#2

Hey @apoorvagupta96
To calculate sieve only till nth prime number you’ll have to calculate it separately for each test case, which would increase the time complexity of the program very much.
Instead it is a very good approach to precompute the sieve and look the nth prime in each test case.
It only uses some extra space, but gives the answer in constant time for each test case.
Hence, it has very less time complexity, and is quite optimized.

#3

okay, thank you for the explanation!

#4

No problem :relaxed:
The code you are using for reference is fine, but try to implement it yourself.