Поиск дружественных чисел

Question

Задача: найти все пары дружественных чисел, меньших 10000. Дружественными называются два числа, если каждое из них равно сумме делителей другого. Равные числа дружественными не считаются.

У меня самого есть 2 кода:

import datetime

a = datetime.datetime.now()

for i in range(1, 10001):
    k = 0
    n = 0
    for x in range(1, i):
        if i % x == 0:
            k += x
    for j in range(1, k):
        if k % j == 0:
            n += j
    if i == n and i < k:
        print(i, k)
print(datetime.datetime.now() - a)

Этот выполняется за 14 с мелочью секунд, но по мне это как-то слишком долго.

import datetime

a = datetime.datetime.now()

for i in range(1, 10001):
    k = sum(filter(lambda x: i % x == 0, range(1, i)))
    n = sum(filter(lambda x: k % x == 0, range(1, k)))
    if i == n and i < k:
        print(i, k)
print(datetime.datetime.now() - a)

Попробовал упростить задачу с помощью анонимных функций и итераторов - на 1 секунду программа выполняется быстрее (что интересно, профайлер Pycharm для первого решения выдает такой же результат (14 сек), но если для второго решения запустить профайлер, то он покажет 27 секунд, а не 13, с чем это связано я не понимаю)

Скорее всего есть решения быстрее, поэтому спрашиваю совета.

Answer 1

Если убрать лишние вычисления и не считать дважды для одного числа, то на моей машине в 3.5 раза быстрее будет:

divsum = [0]*10001

for i in range(1, 10001):
    k = 0
    for x in range(1, 1 + i // 2):
        if i % x == 0:
            k += x
    if k <= 10000:
        divsum[i] = k
        if divsum[k] == i:
            print(i, k)
print(datetime.datetime.now() - a)

А если оптимизировать, считая делители только до корня из числа (парный делитель получить нетрудно), то быстрее в 70 раз:

divsum = [0]*10001

for i in range(1, 10001):
    k = 1
    x = 2
    while  x*x < i:
        if i % x == 0:
            k += x
            k += i//x
        x += 1
    if x*x==i:
        k += x

    if k <= 10000:
        divsum[i] = k
        if k < i and divsum[k] == i:
            print(i, k)

Answer 2

s[i] - сумма всех делителей i кроме него самого. Первый цикл считает суммы сразу для всех чисел из диапазона [1, 10000). Второй цикл ищет и печатает пары дружественных чисел.

n = 10000

s = [1] * n
for i in range(2, n // 2):
    for j in range(2 * i, n, i):
        s[j] += i

for i, j in enumerate(s):
    if i < j < n and s[j] == i:
        print(i, j)

Ускорение примерно в триста раз:

$ time python amicables.py
220 284
1184 1210
2620 2924
5020 5564
6232 6368

real  0m0.042s
user  0m0.044s
sys   0m0.000s

БЛОГ НА HUSL

Поиск дружественных чисел

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