Skip to main content
1 de 6
hkotsubo
  • 66,9mil
  • 25
  • 87
  • 170

Uma pequena otimização é que você não precisa ir até n, basta ir até a raiz quadrada de n.

E para cada divisor que você encontrar, na verdade você encontrou dois divisores. Por exemplo, se o número for 100 e você encontra o divisor 2, você também já encontrou o divisor 50 (resultado de 100 / 2). Então basta somar ambos, economizando uma iteração do loop. Só precisa tomar cuidado para o caso de quadrados perfeitos, para não contar duas vezes o mesmo divisor (por exemplo, se o número for 25, não podemos usar esta lógica com o divisor 5, senão ele será contado duas vezes).

Então ficaria assim:

import math

def soma_divisores(num):
    result = 1 + num
    for i in range(2, int(math.sqrt(num)) + 1):
        d, r = divmod(num, i)
        if r == 0:
            result += i; 
            if i != d:
                result += d; 
    return result

Eu já começo somando 1 e o próprio número (pois ambos sempre serão divisores do número). Depois começo o loop no 2 e vou até a raiz quadrada do número, e aplico a lógica explicada acima. Para isso eu uso divmod, que já retorna o resultado da divisão e o resto desta mesma divisão.


Um pequeno teste usando o módulo timeit já mostra uma diferença significativa:

import math

def sum1(num):
    soma = 0
    for i in range(1, num + 1):
        if num % i == 0:
            soma += i
    return soma

def sum2(num):
    result = 1 + num
    for i in range(2, int(math.sqrt(num)) + 1):
        d, r = divmod(num, i)
        if r == 0:
            result += i; 
            if i != d:
                result += d; 
    return result

import timeit
n = 10 # executa a função 10 vezes
r = 3 # repete por 3 vezes cada execução de n vezes
num = 1000000 # 1 milhão
print(timeit.repeat('sum1(num)', repeat=r, number=n, globals=globals()))
print(timeit.repeat('sum2(num)', repeat=r, number=n, globals=globals()))

A execução varia de máquina para máquina, na minha o resultado foi:

[1.5477205, 1.6962128, 1.5432386]
[0.0020645000000003577, 0.002347499999999947, 0.0021449999999996194]

Ou seja, uma diferença bem grande (os tempos acima estão em segundos).

hkotsubo
  • 66,9mil
  • 25
  • 87
  • 170