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 - potencialmente - 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 100, não podemos usar esta lógica com o divisor 10, 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: # resto zero, é divisor
result += i;
if i != d: # somar também o outro divisor encontrado
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).
Testando com 109, a diferença fica maior ainda (cerca de 3 minutos com o seu código, e 0.007 segundos - 7 milésimos de segundo - com o meu). Mas vale lembrar novamente que os tempos podem variar de acordo com o hardware, se há outras coisas executando na máquina ao mesmo tempo, etc.
Rodando no Repl.it, por exemplo, os tempos foram maiores que na minha máquina, mas a diferença entre os 2 algoritmos continua muito grande (5 minutos do seu código contra 11 centésimos de segundo do meu).