Can someone plz explain why is it so

Here is the solution

https://www.codechef.com/viewsolution/52781930

You need to Precompute the Prime numbers and keep them rather than computing every time for every testcase.

Also for precomputing, use an efficient way such as ‘Sieve of Erathosthenes’.

Thanks for the reply

I have already used “Sieve” approach in my code and also i have now changed it to count the prime numbers only once but still getting TLE.

Here is the solution

https://www.codechef.com/viewsolution/52992996

You are doing Sieve method for every testcase(cuz you are calling **countPrime** for each testcase).

Instead,

Step 1. Create the ‘list of Sieve’ **separately** before Testcase Loop (precompute).

Step 2. Create your ‘countPrime array’ using Sieve array created in step 1 , **separately** before Testcase Loop (precompute).

Then,

in your testcase loop, you can use countPrime ARRAY (Not Function), to

get the number of prime numbers between that range(y, x+1) like **countPrime[y] - countPrime[x+1]** and get your answer.

Your “Sieve” method is being called for every test case ‘t’. More the number of cases, more the time taken.

Instead, initialise your global vector as : `vector<int> arr(1e7+2, 0);`

, and call `Sieve()`

only once, that too before taking any inputs.

This way, with only one function call, all possible prime number counts will be stored in `arr`

.

Check my solution for reference : Solution: 53127524 | CodeChef

I am getting TLE too, even after following everything.

Please help.

https://www.codechef.com/viewsolution/53286071

Change the following

```
while(t-->0)
{
String input[]=br.readLine().split(" ");
x=Integer.parseInt(input[0]);
y=Integer.parseInt(input[1]);
st.isPrime();
s=y-x-(fre[y]-fre[x+1]);
out.write(Integer.toString(s)); out.newLine();
out.flush();
}
```

to

```
st.isPrime();
while(t-->0)
{
String input[]=br.readLine().split(" ");
x=Integer.parseInt(input[0]);
y=Integer.parseInt(input[1]);
s=y-x-(fre[y]-fre[x+1]);
out.write(Integer.toString(s)); out.newLine();
out.flush();
}
```

Oh yes! Thanks a lot…