I am getting a TLE. Please help.

Although my program runs within a time limit 8 sec, yet I receive a time Limit error.
The problem and solution are:


Hey to find exponent of prime p in n! we have a formula Ep(n!) = [n/p] + [n/p²]+…+[n/ps].

If you have any doubt see this

But, why does my program gives a time limit error?

long int n;
for(int i=1;i<=n;i++)//THIS is causing TLE.

N can be upto 10^9, while online judge can perform only K x 10^8 instructions a second. You will easily exhaust you time for larger input, especially when T is (equal to about 100000). In worst case, if i enter numbers ~10^9 T times, you are consuming ~10^14 instructions, which will give you a TLE.

Try to remove that for loop, its possible to do it in logarithmic time.

1 Like