Performatively calculate the divisors of a Python number

Question

The code I’m using is:

import time

def divisores(num):
    for i in range(1, int(num/2+1)):
        if num % i == 0: 
           yield i
    yield num

inicio = time.time()

d = divisores(47587950)
[print(i) for i in d]

print("Fim da execução: %s segundos" % round((time.time() - inicio),2))

The return: Fim da execução: 5.94 segundos. That code is slow.

There is a more performative way to calculate divisors of a number using Python?

Answer 1

Tip: Don’t use list comprehensions to perform functions such as the print(), append() etc... will create a temporary list full of values None, and has performance implications if this is too big, you can test this by doing print(print('hey')) whose print will print the return of the print inside (which is None), REF.

In terms of performance there is not much to do and your implementation is largely well done:

Way 1:

def divisores(num):
    for i in range(1, num//2+1):
        if num % i == 0: 
            yield i
    yield num

num = 47587950
print(list(divisores(num)))

Way 2:

num = 47587950
print([i for i in range(1, num//2+1) if num%i==0])

As for the performance the first way can be a little faster, and if you do not turn it into list is almost instantaneous:

DEMONSTRATION

In the above demonstration:

• using the way 1 we have a time of 1.7259 secs
• using the way 2 we took our time 1.9021 secs

Remembering that on your computer you should run faster than on Ideone.

Using the function of Way 1 the most suitable for printing one at a time would be:

...
num = 47587950
for d in divisores(num):
    print(d)

Answer 2

Yes, you can optimize quite a lot.

If you found a divider, then you actually found - in most cases - two. For example, if the number is 100 and I found the divisor 2, then I also found the divisor 50 (result of 100 / 2). With this I save an iteration of for for each divisor found.

The only exception is when the number is a perfect square: if the number is 100 and I found the divisor 10, I cannot consider that 100 / 10 is another divisor, otherwise I will be counting the 10 twice.

Another detail is that, in doing so, the iteration can go to the square root of the number, instead of going halfway. For if a certain number n has splitters, so it can be written as the product a * b (whereas a and b are dividers of n). If both (both a how much b) are larger than the square root of n, then a * b would be greater than n, so one of them has to be smaller than the square root. So if I found one of them (the smaller than the square root), I have also found the larger, as already described above. Therefore the loop can go to the square root.

Would look like this:

from math import sqrt

def divisores(num):
    yield 1 # 1 é divisor de qualquer número
    for i in range(2, int(sqrt(num)) + 1):
        if num % i == 0:
            yield i # encontrei um divisor
            outro_divisor = num // i
            if outro_divisor != i: # não é quadrado perfeito
                yield outro_divisor # retorna o outro divisor
    yield num # o próprio número é divisor dele mesmo

One detail is that the dividers will not be in ascending order, but then it would be enough to order them (sorted(divisores(num))).

---

Doing a test with the module timeit and comparing with the solutions of the other answers:

# loop simples (testa um a um)
def divisores(num):
    for i in range(1, num // 2 + 1):
        if num % i == 0: 
            yield i
    yield num

# otimizado (conforme descrição acima)
from math import sqrt
def divisores_otimizado(num):
    yield 1 # 1 é divisor de qualquer número
    for i in range(2, int(sqrt(num)) + 1):
        if num % i == 0:
            yield i
            outro_divisor = num // i
            if outro_divisor != i:
                yield outro_divisor
    yield num

# numpy, sugestão de uma das respostas
import numpy as np
def divisores_numpy(num):
    n = np.arange(1,num)
    d = num % n
    zeros = d == 0
    return n[zeros]

from timeit import timeit

# executa 1 vez cada teste
params = { 'number' : 1, 'globals': globals() }

num = 47587950
# loop simples
print(timeit('for _ in divisores(num): pass', **params))
# numpy
print(timeit('for _ in divisores_numpy(num): pass', **params))
# meu código
print(timeit('for _ in divisores_otimizado(num): pass', **params))
# meu código, porém ordenando o resultado
print(timeit('for _ in sorted(divisores_otimizado(num)): pass', **params))

The timeit returns time in seconds, and of course it varies from one machine to another, as it depends on several factors (hardware, if there were other things running on the machine, etc). But anyway, in mine I got close results of this:

3.7604584
0.2803169999999997
0.0007887000000001976
0.0007956000000000074

That is, the loop simple testing one by one took more than 3 seconds, the numpy It took less than 3 tenths of a second, and my code took less than 800 microseconds (that is, less than 0.8 milliseconds). The version that sorts the divisors was a little slower, but since the divisor list is small (in this case, it has only 36 numbers), the sort does not interfere so much with the final result (there was an increase of a few microseconds).

That is, this solution (whether ordering or not) was around 4700 times faster than the loop simple and about 350 times faster than the numpy. Testing on Ideone.com and in the Repl.it, times change, but the results are similar: numpy slower, and the loop simple much slower still (Obs: no Repl.it had to test with a smaller number because the numpy was apparently bursting the memory).

---

The difference is great because the larger the number in question, the greater the difference between the number of iterations made. In this case, the number is 47587950 (more than 47 million). The loop simple goes up to half the number, so more than 23 million iterations are made. The optimized algorithm goes to the square root of the number, only making 6898 iterations - that is, about 3400 times less iterations.

And the higher the number, the more this difference increases (for example, if the number is 100 million, it will be 50 million iterations in the loop simple versus 10,000 iterations in optimized - about 7200 times less iterations). And in the case of numpy, no matter how fast he is, is still being created an array with millions of elements and iterating for all, so it is also slower.

Answer 3

Numpy was born for it:

import numpy as np
import time

def divisores(num):
    n = np.arange(1,num)
    d = num % n
    zeros = d == 0
    print (n[zeros])

inicio = time.time()
divisores(47587950)
print("Fim da execução: %s segundos" % round((time.time() - inicio),2))  

Exit:

[       1        2        3        5        6        9       10       15
       18       25       30       45       50       75       90      150
      225      450   105751   211502   317253   528755   634506   951759
  1057510  1586265  1903518  2643775  3172530  4758795  5287550  7931325
  9517590 15862650 23793975]  
Fim da execução: 0.99 segundos

It took 0.99 seconds here.

Answer 4

a = 1
num = int(input("Digite o número: "))
while a <= num:
    x = num % a
    a = a +1
    if x == 0:
        print (a-1)