please tell me why it is giving me tle,although output and algo is correct

http://www.codechef.com/viewsolution/4326949

for(k=2;k<=n-j+1;k++)

{max=0;

if(primes[k])

{

for(i=1;i<=j;i++)

{count=0;

while((ar[i]%k)==0)

{count=count+1;

ar[i]= ar[i]/k;

}

if(count > max)

max=count;

}

in this code you are running your code for each k,then what is the profit of finding the primes.Try creating a separate array of primes to which has only primes ,nothing else than it will make your loop to go fasterâ€¦

Also use modular exponentiation to calculate power.

See here.

modular exponentiation is not needed here, my solution got AC w/ .04sec doing just a regular O(n) exponentiation. Using modular exponentiation my solution passed in .04sec as well, so the exponentiation makes no difference here.

a mathematical proof: the biggest prime power would be log(1e6)/log(2)=19, so doing O(n) or O(log n) for n < 19 wouldnâ€™t make the slightest difference