O
Take away the divisions. elem On the list, leave it. range(1, (i+1))And then it'll work.1.5 milliseconds. I don't think optimizing is necessary.import time
t1 = time.time()
def list_squared(m, n):
need_numbers = []
for i in range(m, n):
divisors = [elem*elem for elem in range(1, (i+1)) if i % elem == 0 ]
da = sum(divisors)**(0.5)
if da.is_integer():
need_numbers.append([i, sum(divisors)])
return need_numbers
print(list_squared(1, 250))
t2 = time.time()
print(t2-t1)
Conclusion:[[1, 1], [42, 2500], [246, 84100]]
0.0015308856964111328
UPDATETopik Starter asked for an optimised solution. Okay.The optimized solution is used by the fact that all businessmen n is made of the same simple numbers as the number n♪ For example, 300 1, 5, 25, 3, 15, 75, 2, 10, 50, 6, 30, 150, 4, 20, 100, 12, 60, 300 are divided only by 2.3.5. That's the one that's clear.Therefore, to speed up the account, the number should be separated. n to ordinary multipliers, find for each multiplier the extent to which it divides the number n and build all the combinations of simple thumbs.Example300 = 22 * 3 * 52So the dealers will: 1, 21, 22, 3, 23, 22 * 3, 5, 22 * 5, 235, 22 35, 52, 22 * 52, 2352, 22 35**2, 35, 3 * 5**2♪import math
Список простых чисел, меньших 1000
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23,
29, 31, 37, 41, 43, 47, 53, 59, 61, 67,
71, 73, 79, 83, 89, 97, 101, 103, 107, 109,
113, 127, 131, 137, 139, 149, 151, 157, 163, 167,
173, 179, 181, 191, 193, 197, 199, 211, 223, 227,
229, 233, 239, 241, 251, 257, 263, 269, 271, 277,
281, 283, 293, 307, 311, 313, 317, 331, 337, 347,
349, 353, 359, 367, 373, 379, 383, 389, 397, 401,
409, 419, 421, 431, 433, 439, 443, 449, 457, 461,
463, 467, 479, 487, 491, 499, 503, 509, 521, 523,
541, 547, 557, 563, 569, 571, 577, 587, 593, 599,
601, 607, 613, 617, 619, 631, 641, 643, 647, 653,
659, 661, 673, 677, 683, 691, 701, 709, 719, 727,
733, 739, 743, 751, 757, 761, 769, 773, 787, 797,
809, 811, 821, 823, 827, 829, 839, 853, 857, 859,
863, 877, 881, 883, 887, 907, 911, 919, 929, 937,
941, 947, 953, 967, 971, 977, 983, 991, 997]
def find_prime_divisor(n):
"Функция наименьший простой делитель числа n"
lim = math.floor(math.sqrt(n+1))
# Сначала проверим простые из списка
for p in primes:
if p > lim:
# p*p > n -- дальше перебирать бессмысленно, n не делится на такое большое p
break
if n%p == 0:
# Нашли делитель
return p
if p > lim:
# n меньше миллиона, и не делится ни на одно простое из списка
# следовательно, n - простое
return n
# n больше миллиона. Ищем его делители лобовым перебором.
for m in range(p, n,2):
if n%m == 0:
return m
# делители не найдены. n - простое число
return n
def get_divisor_degree(m,n):
"""Функция возвращает максимальную степень d числа m, при которой md делит n
Возвращается пара (d, n/md)
"""
deg = 0
while n%m == 0:
deg += 1
n //= m
return deg, n
def factorize(n):
"""Функция раскладывает n на простые множители.
Возвращается набор пар (простой_делитель, степень_делителя) в виде словаря."""
factors = {}
while n > 1:
p = find_prime_divisor(n)
deg, n = get_divisor_degree(p,n)
factors[p] = deg
return factors
def gen_divisors(factors):
"""Генератор делителей из списка пар (простой_делитель, степень_делителя)"""
if isinstance(factors, dict):
factors = list(factors.items())
if len(factors) == 0:
# Пустой список - вовзращаем 1
yield 1
else:
# вынимает первый делитель из списка
p, deg = factors[0]
p_m = 1
for _ in range(deg+1):
# генерируем делители из остальных простых делителей
# и умножаем их последовательно на степени p
for div in gen_divisors(factors[1:]):
yield p_m*div
p_m = p
def list_divisors(n):
'''Функция возвращает список всех делителей числа n'''
return list(gen_divisors(factorize(n)))
def is_square(n):
"Функция возвращает True, если целое число n является квадратом другого целого числа."
root = math.floor(math.sqrt(n+1))
return rootroot == n
is_square(625), is_square(101)
(True, False)
def check_number(n):
"Функция возвращает True если число подходит под условие задачи, и сумму квадратов делителей"
divs = list_divisors(n)
divs_square = sum(map(lambda x:x*x, divs))
return is_square(divs_square), divs_square
def run(iterable):
"Функция проверяет каждое число из итератора и генерирует пары (число, сумма квадратов делителей) для подходящих"
for n in iterable:
good, divs_square = check_number(n)
if good:
yield n, divs_square
print(list(run(range(1, 10000))))
Conclusion:[(1, 1), (42, 2500), (246, 84100), (287, 84100), (728, 722500), (1434, 2856100), (1673, 2856100), (1880, 4884100), (4264, 24304900), (6237, 45024100), (9799, 96079204), (9855, 113635600)]
Work time is 130-150 milliseconds. I didn't wait to decide. https://github.com/pakuula/StackOverflow/blob/main/python/1265671/square_divs.ipynb Optimized solution loses decision at intervals [1, 500] And it's hard to win at intervals longer than [1,1000]
