getting TLE , help plz

Problem :- http://www.codechef.com/problems/D1/

C++ solution:- http://ideone.com/rHBBrW
Java solution:- http://ideone.com/Odb6hT

Fact is that i am getting TLE while submitting code in C++ and in am getting wrong answer while submitting code in java .But code is exactly same(no change in code).
I just implemented the editorial given of the problem.

Plz anyone help…

First of all,
I think you must be knowing that if your code is giving TLE then it doesn’t mean it is correct but takes too long. TLE simply means you exceeded the time limit. Your program never finished running in time - so Codechef has no idea whether it was going to print out the right results or not!

if your java code is giving WA it meas your c++ code will also give WA.

Now about your C++ code (I don’t know much about JAVA)
Loops: You are using too many loops (remember loops are lazy). For ex your code

void Calculate_primes() {
        for (int i = 0; i <= MAX; i++) {
            arr[i] = true;
        }

It runs till 500000. you don’t need that you can use static int arr[some_no] to set a 0 value in array another option memset(arr).

How to resolve TLE ?

  • Simply look at your code you are
    using so many loops.
  • Take some time and review your code.
  • (Important) long long makes your code slower. Use it Wisely

I think this approach can be used:
1> For each N- get the square root of N.
2> Check if N is prime then answer 1
3> If not prime check till root N all the factors of N and store each new factors.

For Example : N=12
Root N = 3 (floor root N)
26=12
3
4 =12

So all the multiples of 12 are 1,2,3,4,6.

Please Upvote and mark it as your answer IF IT HELPED YOU.

Happy Coding :slight_smile:

3 Likes
//