Sim, dá para otimizar bastante.
Se você encontrou um divisor, então na verdade encontrou - na maioria dos casos - dois. Por exemplo, se o número for 100 e eu encontrei o divisor 2, então eu também encontrei o divisor 50 (resultado de 100 / 2). Com isso eu economizo uma iteração do for
para cada divisor encontrado.
A única exceção é quando o número é um quadrado perfeito: se o número for 100 e eu encontrei o divisor 10, não posso considerar que 100 / 10 é outro divisor, senão estarei contando o 10 duas vezes.
Outro detalhe é que, fazendo desta forma, a iteração pode ir até a raiz quadrada do número, em vez de ir até a metade. Pois se um determinado número n
possui divisores, então ele pode ser escrito como o produto a * b
(sendo que a
e b
são divisores de n
). Se ambos (tanto a
quanto b
) forem maiores que a raiz quadrada de n
, então a * b
seria maior que n
, por isso um deles tem que ser menor que a raiz quadrada. Então se eu encontrei um deles (o menor que a raiz quadrada), também já encontrei o maior, como já descrito acima. Por isso o loop pode ir até a raiz quadrada.
Ficaria assim:
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
Um detalhe é que os divisores não estarão em ordem crescente, mas aí bastaria ordená-los (sorted(divisores(num))
).
Fazendo um teste com o módulo timeit
e comparando com as soluções das outras respostas:
# 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))
O timeit
retorna o tempo em segundos, e claro que ele varia de uma máquina para outra, pois depende de vários fatores (hardware, se havia outras coisas rodando na máquina, etc). Mas enfim, na minha eu obtive resultados próximos disso:
3.7604584
0.2803169999999997
0.0007887000000001976
0.0007956000000000074
Ou seja, o loop simples que testa um por um demorou mais de 3 segundos, o numpy
demorou menos que 3 décimos de segundo, e o meu código demorou menos que 800 microssegundos (ou seja, menos que 0,8 milissegundos). A versão que ordena os divisores foi um pouco mais lenta, mas como a lista de divisores é pequena (no caso, tem apenas 36 números), a ordenação não interfere tanto no resultado final (houve um aumento de poucos microssegundos).
Ou seja, esta solução (seja ordenando ou não) foi por volta de 4700 vezes mais rápida do que o loop simples e cerca de 350 vezes mais rápida que o numpy
. Testando no IdeOne.com e no Repl.it, os tempos mudam, mas os resultados são similares: numpy
mais lento, e o loop simples muito mais lento ainda (obs: no Repl.it tive que testar com um número menor porque o numpy
estava aparentemente estourando a memória).
A diferença é grande porque quanto maior o número em questão, maior é a diferença entre a quantidade de iterações feitas. No caso, o número é 47587950 (mais de 47 milhões). O loop simples vai até a metade do número, portanto são feitas mais de 23 milhões de iterações. Já o algoritmo otimizado vai até a raiz quadrada do número, fazendo apenas 6898 iterações - ou seja, cerca de 3400 vezes menos iterações.
E quanto maior o número, mais essa diferença aumenta (por exemplo, se o número for 100 milhões, serão 50 milhões de iterações no loop simples contra 10 mil iterações no otimizado - cerca de 7200 vezes menos iterações). E no caso do numpy
, por mais rápido que ele seja, ainda está sendo criado um array com milhões de elementos e iterando por todos, por isso também é mais lento.
De forma geral, os outros algoritmos possuem complexidade O(n) (chamada de linear), enquanto que o algoritmo acima possui complexidade O(n1/2) (também chamada de sub-linear). Por isso a quantidade de operações cresce bem menos (proporcionalmente ao tamanho da entrada) se comparado com os algoritmos das outras respostas. Usando o exemplo dos parágrafos acima, ao usar um número cerca de 2 vezes maior (ou seja, aumentei de 47 milhões para 100 milhões), as iterações do algoritmo otimizado aumentam apenas cerca de 45%. Sem contar, é claro, a quantidade total de iterações com relação ao número original, que faz com que a diferença de desempenho seja tão grande.