"Prateek loves candy" TLE

#1

I have used sieve of eratosthenes. still it is showing timelimit.
Code: https://ide.codingblocks.com/s/116001

#2

@Kishan-Mishra-2464674013761441
Since there are 10000 testcases involved , we should further optimise this code. Make an array/vector of integers and store the prime numbers in it.
Let’s call it primes.
Whenever you hit the if condition in Line No. 42 , insert the element i into primes.
primes.push_back(i);
That way when you are done with sieve , you not only have the sieve array ready but also an array of prime numbers ready. Now just print primes[n] or primes[n-1] ( Bases on how you keep the indexing) . No need to compute the nth prime everytime.
Do not forget to push 2 into the primes array before running the loop as 2 is the first prime number.

1 Like