CHEFMGX....My code is giving TLE

help
1

Can someone plz explain why is it so
Here is the solution
https://www.codechef.com/viewsolution/52781930

2

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
3

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

4

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
5

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 : CodeChef: Practical coding for everyone

1 Like
6

I am getting TLE too, even after following everything.
Please help.
https://www.codechef.com/viewsolution/53286071

7

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
8

Oh yes! Thanks a lot…