CHEFMGX :: TLE error :: Need Suggestion

1

can anybody explain me where i am going wrong with the solution and tell me about the concept to learn in order to optimize the solution
#beginner

solution : CodeChef: Practical coding for everyone

1 Like
2

Let’s see…

while (X!=Y){
    for (i=1;i<=X+2;i++){
        if((X+2)%i==0 && X+2<=Y) {
             p++;
        }
    }
    if(p==2) { 
        X=X+2;
    }
    else{
	    X=X+1;
    }
    p=0;
    np++;
}

Your method to find whether X+2 is prime has a Time Complexity of O(X). You are doing this for potentially every X in the range [X,Y].

Now the range [X, Y] is 107 and you run your prime check which also has an upper bound of 107. So the total operations come to around 1014.

This is what gives you TLE.

Hint 1:is there a faster algorithm to find all the primes in a given range?
Hint 2: Does pre-computing the number of primes in a given range help us solve the problem?
3 Likes
3

Thankyou for the explaination :slight_smile:

4

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