Дружественные числа.Как оптимизация перебор?(Python)

Question

def sumNumDivs(num):
divs_sum = -num
div = 1
while div * div <= num:
    if num % div == 0:
        if div == num // div:
            divs_sum += div
        else:
            divs_sum += div
            divs_sum += num // div
    div += 1
return divs_sum

first, last = map(int, input().split())
c = 0
for z in range(first, last + 1):
    for k in range(z+1, last + 1):
        if sumNumDivs(z) == k and sumNumDivs(k) == z:
            print("(", z, ',', k, ")", sep='', end=' ')
            c += 1
if c < 1:
    print(0)

Как сократить время работы?Я так понимаю проблема в переборе и сравнении.

Answer 1

Если Вы добавите счетчик к вызовам функции sumNumDivs, то увидите, что она вызывается очень много раз для тех же самых чисел. А это явный признак сделать "мемоизацию". Есть много техник, но в данном случае хорошо так, после функции sumNumDivs добавляем такое:

def memoize(f):
    memo = {}
    def helper(x):
        if x not in memo:            
            memo[x] = f(x)
        return memo[x]
    return helper

sumNumDivs = memoize(sumNumDivs)

запускаем и наслаждаемся.

По факту, можно вначале просто пройтись по числам и сделать массив кол-ва делителей. А потом уже по нему смотреть. Это может оказаться сильно быстрее.

БЛОГ НА HUSL

Дружественные числа.Как оптимизация перебор?(Python)

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