I was trying to solve 150A and I submitted a solution where I used a variable ( i ) in a loop :
for(int i=2; i*i<=n; i++)
{
while(n%i == 0)
{
n /= i;
p[k++] = i;
}
}
and it got TLE in test 7
submission : 32983991
and when I changed the datatype of variable ( i ) to long long it got accepted.
submission : 32984272
can anyone help me with the reason...?
When "i" is an int, the calculation "i*i" will result in an overflow, producing a negative number, which will always be less than "n". It gets TLE because of the infinite loop...
thank you :D
the limit on n is 1013. i is an integer, and it cannot be higher than 231 - 1, so it will never exceed n if n is high enough. You basically ran an infinite loop.
Edit: I was too late :P