Time limit exceed

#1

time limit is exceeding in the test case
here is my code-

#2

Hello @pragyachoudhary1111,

if you look at total iterations in worst case:
t=10000 and N=100000007
So, total iterations=t*N=10^12, which is exceeding the time limit.

Solution:

  1. It, is mentioned in the question that the answer would not exceed 10^6, So, N should be 10^6.

  2. Take extra memory.
    Create that stores the nth prime number at (n-1)th index.
    i.e. prime[0]=2, prime[1]=3 and so on.

This would reduced the searching time to O(1) i.e. constant time.
Because now you can find the nth prime from the prime array directly eliminating the need of for loop.

Declare, this array inside the main function and fill the primes numbers to it inside the sieves function using the array p.

Let me know if you don’t understand something.

Hope, this would help.
Give a like, if you are satisfied.