How to quickly calculate the sum of dividers in Python?

Question

I would like to know how to quickly calculate the sum of the divisors of a natural number n, where 2 <= n < 10⁹. For small numbers, I perform this operation quietly with the following code:

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

But for very large numbers my code is not efficient.

Answer 1

A small optimization is that you don’t need to go up n, just go to the square root of n.

And for every splitter you find, you actually found - potentially - two splitters. For example, if the number is 100 and you find the divisor 2, you have also found the divisor 50 (result of 100 / 2). So just add them both together, saving an iteration of the loop. Just take care for the case of perfect squares, not to count the same divisor twice (for example, if the number is 100, we cannot use this logic with the divisor 10, otherwise it will be counted twice).

Then it would look like this:

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

I already start by adding 1 and the number itself (for both will always be number dividers). Then I start the loop in 2 and I go to the square root of the number, and apply the logic explained above. For this I use divmod, which already returns the result of the division and the rest of this same division.

---

A little test using the module timeit already shows a significant difference:

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

The execution varies from machine to machine, in my the result was:

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

That is, a very big difference (the above times are in seconds).
Testing with 10⁹, the difference gets even bigger (about 3 minutes with your code, and 0.007 seconds - 7 thousandths of a second - with mine). But remember again that times may vary according to hardware, if there are other things running on the machine at the same time, etc.

Running on the Repl.it, for example, times were higher than on my machine, but the difference between the 2 algorithms remains very large (5 minutes of your code against 11 hundredths of a second of my).