CHEFMGX....My code is giving TLE

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’.

2 Likes

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. :ok_hand:

2 Likes

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

1 Like

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(); 
            }
1 Like

Oh yes! Thanks a lot…