Quote:

I got TLE in UVA. It was obvious to get TLE.

This problem is worded the way of challenges sites,

**you need to know the strait forward solutions (or brute force) are never the solution.**
You need to have deep understanding of the problem in order to apply algorithm simplifications and make your solution faster.

In this code, for any

`N`

, you loop

`N`

times: O(N)=N

for(int i=1; i<=n; i++) {

In this code, for any

`N`

, you loop

`√N`

times: O(N)=√N

for(int i=1; i*i<n; i++) {

But there is a multiplication on every loop.

In this code,

`√N`

multiplications are replace by a single square root function.

Top=int(sqrt(N)
for(int i=1; i<=Top; i++) {

You need to take advantage of any possible shortcut in you code:

Everytime you find a divisor

`i`

of

`N`

, it imply that

`N/I`

is also a divisor of

`N`

, without further checking.

This code:

if(n%i==0 && i%k!=0)sum+=i;
if(n%(n/i)==0 && (n/i)%k!=0)sum+=(n/i);

translate as

if(n%i==0 ){
if(i%k!=0)sum+=i;
if((n/i)%k!=0)sum+=(n/i);
}
And there is more to find.

You also may want to play with the list of prime factors of the number.