# How can I make this code more efficent for the coding challenge?

I am doing coding challenge named Integers: Recreation One in Codewars.

Challenge => Given two integers m, n (1 <= m <= n) we want to find all integers between m and n whose sum of squared divisors is itself a square.

``````def list_squared(m, n):
lst = list()
for num in range(m, n+1):
total= 0
for i in range(1, num//2 +1):
if num % i == 0:
total += i**2
total += num**2

if (total**(1/2)) % 1 == 0:
lst.append([num, total])

return lst
``````

My code works for sample tests but when I try to submit it, it is giving me " Execution Timed Out " error. I think I have to make this more efficent but don't know how to do it. How can I make the code more efficent? On Best Solutions

An implementation of the `sqrt` idea:

``````def list_squared(m, n):
lst = list()
for num in range(m, n+1):
total = 0
sqrt = int(math.sqrt(num))
for i in range(1, sqrt+1):
q,r=divmod(num,i)
if r == 0:
total += i*i + q*q
if sqrt*sqrt == num:
total -= num

if math.sqrt(total) % 1 == 0:
lst.append([num, total])

return lst
``````

It seems to work. A couple things which may or may not make sense:

• I do not know if `**(1/2)` or `math.sqrt` performs better, it could be checked. However I feel `sqrt` is more readable. Of course if you are not allowed to use the math library, stick with `**`
• It is rather probable that `x*x` is faster than `x**2`, it could be checked too
• At assembly level, the quotient and the remainder are produced in a single step, which may or may not be true for Python. However this is why I used `divmod` (so `q*q` replaces `(num/i)*(num/i)`, or `(num/i)**2`)

In reality these details probably do not matter at all, shortening the inner loop should be the main trick.

@H.E.K.: you "felt" that the loop can be shortened somehow, via the `/2` thing, but in reality it has to be square root.
If `i` is divisor of `num`, `num/i` is also a divisor of `num`. And if `i` starts increasing from `1`, `num/i` starts decreasing from `num/1` (so from `num` itself). As time passes, they will meet somewhere, and that is `sqrt(num)`. Increasing `i` above `sqrt(num)` ends up with checking a divisor-pair which you have seen already. An example with 20:

``````i   20/i
1   20
2   10
3   <something fraction>
4   5    <--- this is the last step when we encounter a new divisor
5   4    <--- here the divisors are "old", we have seen 4 and 5 already
6   <something fraction>
......
``````

so the divisors are 1,20,2,10,4,5 - and we did not have to check 5...20 separately, it was enough to check `1...4=(int)sqrt(20)`, which is a significant gain.