Найти число, сумма квадратов делителей которого является квадратом целого числа

Нужно найти все такие числа в интервале от 1 до 250.

РЕШЕНИЕ РАБОТАЕТ, просто нужно оптимизировать

codewars не принимает из за времени выполнения(

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)/elem) 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)

Ответы (1 шт):

Автор решения: Pak Uula

Уберите деление на elem в списке, оставьте range(1, (i+1)), и тогда всё заработает.

Время счёта 1.5 миллисекунды. Мне кажется, оптимизировать нет необходимости.

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)

Вывод:

[[1, 1], [42, 2500], [246, 84100]]
0.0015308856964111328

UPDATE

Топик-стартер попросил оптимизированное решение. Ок.

Оптимизированное решение использует тот факт, что все делители числа n состоят из тех же простых чисел, что делят само число n. Например, делители числа 300 1, 5, 25, 3, 15, 75, 2, 10, 50, 6, 30, 150, 4, 20, 100, 12, 60, 300 сами делятся только на 2,3,5. Ну и единица, понятное дело.

Поэтому для ускорения счёта нужно разложить число n на простые множители, найти для каждого множителя с какой степенью оно делит число n и построить все комбинации произведений простых сомножителей.

Пример 300 = 2**2 * 3 * 5**2 Значит, делителями будут: 1, 2**1, 2**2, 3, 2*3, 2**2 * 3, 5, 2**2 * 5, 2*3*5, 2**2 *3*5, 5**2, 2**2 * 5**2, 2*3*5**2, 2**2 *3*5**2, 3*5, 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, при которой m**d делит n
    Возвращается пара (d, n/m**d)
    """
    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  root*root == 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))))

Вывод:

[(1, 1), (42, 2500), (246, 84100), (287, 84100), (728, 722500), (1434, 2856100), (1673, 2856100), (1880, 4884100), (4264, 24304900), (6237, 45024100), (9799, 96079204), (9855, 113635600)]

Время работы 130-150 миллисекунд. Решение в лоб я не дождался.

Jupyter Notebook с решением

Оптимизированное решение проигрывает решению в лоб на интервале [1, 500] и твёрдо выигрывает на интервалах длиннее чем [1,1000]

→ Ссылка