python - How to improve my slow nested for loops with itertools?

Question

My Code for a Codewars Problem is just way too slow, after some research it seems I have to use itertools product BUT I can't figure out a way how

Right now this is my code, which does work but as said way too slow.

def list_squared(m, n):
  results = []
  for i in range (m, n):
     sum = 0
     for j in range (1, i+1):
         if i % j == 0:
             sum += j**2
     if int(sum**(1/2))**2 == sum: #checking if number is a perfect square number
             results.append([i, sum])
  return results

How do I use the prodcut function from itertools here in this case ?

EDIT: Some Examples:

list_squared(1, 250) --> [[1, 1], [42, 2500], [246, 84100]]

list_squared(42, 250) --> [[42, 2500], [246, 84100]]

I should get a list like that. Given my input of two integers m, n (1 <= m <= n) I want to find all integers between m and n whose sum of squared divisors is itself a square.

For Example: Divisors of 42 are : 1, 2, 3, 6, 7, 14, 21, 42. These divisors squared are: 1, 4, 9, 36, 49, 196, 441, 1764. The sum of the squared divisors is 2500 which is 50 * 50, a square!

question from:https://stackoverflow.com/questions/65947902/how-to-improve-my-slow-nested-for-loops-with-itertools

Answer 1

If "sum**(1/2)" means "square root of sum", it is probably being translated automagically into something like exp((1/2)*log(sum)), which is going to eat you alive. For breakfast. Without salt.

The modulo operation i % j is probably not helping, but that's most certainly a few mosquito bites after the wolves get finished with you.

This is one of those times where you have to take a long, hard look at your algorithm.

Start by observing that the set of perfect squares <= n, for all non-trivial, is very much smaller than the set of integers <= n.

(HINT: 1, 4, 9, 16, 25, 36, 49, 64, ... as opposed to 1, 2, 3, ..., 64, ...)

I'd also look at the way I was generating the j values. Those appear at first glance to be factors of the i values.