c++ - ICPC Live Archive 5110.. Time Limit Exceeded -

c++ - ICPC Live Archive 5110.. Time Limit Exceeded -

this problem icpc 2010 regionals.

problem name: square free number

why code getting tle used minimal number of loops ? please help...

problem link :

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&itemid=8&category=380&page=show_problem&problem=3111

my code:

#include <stdio.h> #include <math.h> int main() { int t; scanf("%d", &t); while(t--) { long long int n,k; scanf("%lld", &n); int i,j,power,mx; mx = 0; for(i = 2; < n; i++) { if(n % == 0) { long long int m = n; powerfulness = 0; while(1) { int temp= m; m = m/i; if(m*i == temp) { power++; } else { break; } } if(power >= mx) { mx = power; } } } if(mx == 0) { mx++; } printf("%d\n", mx); } homecoming 0; }

there 3 levels of loops in code:

while(t--) for(i = 2; < n; i++) while(1)

the first 2 loop lead repeat of n*t times, , according problem description that's 1e10 times in worst case. result in tle on online judges.

solution: alter algorithm.

c++ c optimization