2

Gostaria de saber como calcular, de forma rápida, a soma dos divisores de um número natural n, sendo 2 <= n < 109. Para números pequenos, realizo esta operação tranquilamente com o seguinte código:

n = int(input())
for c in range(1, n + 1):
    m = int(input())
    soma = 0
    for i in range(1, m + 1):
        if m % i == 0:
            soma += i
    print('{}'.format(soma)) 

Mas para números muito grandes o meu código não é eficiente.

1

1 Resposta 1

1

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).

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .