Qual é a maneira mais eficiente de encontrar todos os fatores de um número no Python?

Alguém pode me explicar uma maneira eficiente de encontrar todos os fatores de um número no Python (2.7)?

Posso criar um algoritmo para fazer isso, mas acho que é mal codificado e leva muito tempo para produzir um resultado para um grande número.

from functools import reduce

def factors(n):    
    return set(reduce(list.__add__, 
                ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))

Isso retornará todos os fatores, muito rapidamente, de um número n.

Por que raiz quadrada como o limite superior?

sqrt(x) * sqrt(x) = x. Portanto, se os dois fatores são iguais, ambos são a raiz quadrada. Se você aumentar um fator, precisará diminuir o outro. Isso significa que um dos dois sempre será menor ou igual a sqrt(x), portanto, você só precisa procurar até esse ponto para encontrar um dos dois fatores correspondentes. Você pode usar x / fac1para obter fac2.

A reduce(list.__add__, ...)é tomar as pequenas listas de [fac1, fac2]e unindo-os em uma lista longa.

O [i, n/i] for i in range(1, int(sqrt(n)) + 1) if n % i == 0retorna um par de fatores se o restante quando você dividir npelo menor for zero (ele também não precisa verificar o maior; apenas obtém isso dividindo npelo menor).

O set(...)lado de fora está se livrando de duplicatas, o que só acontece com quadrados perfeitos. Pois n = 4, isso retornará 2duas vezes, para setse livrar de um deles.

A solução apresentada pelo @agf é ótima, mas é possível obter um tempo de execução ~ 50% mais rápido para um número ímpar arbitrário , verificando a paridade. Como os fatores de um número ímpar sempre são ímpares, não é necessário verificá-los ao lidar com números ímpares.

Acabei de começar a resolver os enigmas do Project Euler . Em alguns problemas, uma verificação do divisor é chamada dentro de dois forloops aninhados , e o desempenho dessa função é essencial.

Combinando esse fato com a excelente solução da agf, acabei com esta função:

from math import sqrt
def factors(n):
        step = 2 if n%2 else 1
        return set(reduce(list.__add__,
                    ([i, n//i] for i in range(1, int(sqrt(n))+1, step) if n % i == 0)))

No entanto, em números pequenos (~ <100), a sobrecarga extra dessa alteração pode levar a função a demorar mais.

Fiz alguns testes para verificar a velocidade. Abaixo está o código usado. Para produzir as diferentes parcelas, alterei a mesma X = range(1,100,1).

import timeit
from math import sqrt
from matplotlib.pyplot import plot, legend, show

def factors_1(n):
    step = 2 if n%2 else 1
    return set(reduce(list.__add__,
                ([i, n//i] for i in range(1, int(sqrt(n))+1, step) if n % i == 0)))

def factors_2(n):
    return set(reduce(list.__add__,
                ([i, n//i] for i in range(1, int(sqrt(n)) + 1) if n % i == 0)))

X = range(1,100000,1000)
Y = []
for i in X:
    f_1 = timeit.timeit('factors_1({})'.format(i), setup='from __main__ import factors_1', number=10000)
    f_2 = timeit.timeit('factors_2({})'.format(i), setup='from __main__ import factors_2', number=10000)
    Y.append(f_1/f_2)
plot(X,Y, label='Running time with/without parity check')
legend()
show()

X = intervalo (1.100,1)

Não há diferença significativa aqui, mas com números maiores, a vantagem é óbvia:

X = intervalo (1.100.000.1000) (apenas números ímpares)

X = intervalo (2.100.000.100) (apenas números pares)

X = intervalo (1.100.000.1001) (paridade alternada)

A resposta da agf é realmente muito legal. Eu queria ver se poderia reescrevê-lo para evitar o uso reduce(). Isto é o que eu vim com:

import itertools
flatten_iter = itertools.chain.from_iterable
def factors(n):
    return set(flatten_iter((i, n//i) 
                for i in range(1, int(n**0.5)+1) if n % i == 0))

Eu também tentei uma versão que usa funções complicadas de gerador:

def factors(n):
    return set(x for tup in ([i, n//i] 
                for i in range(1, int(n**0.5)+1) if n % i == 0) for x in tup)

Eu cronometrei isso computando:

start = 10000000
end = start + 40000
for n in range(start, end):
    factors(n)

Eu o executei uma vez para permitir que o Python o compilasse, depois executei o comando time (1) três vezes e mantenha o melhor tempo.

• reduzir versão: 11.58 segundos
• versão do itertools: 11.49 segundos
• versão complicada: 11.12 segundos

Observe que a versão do itertools está construindo uma tupla e transmitindo-a para flatten_iter (). Se eu alterar o código para criar uma lista, ele diminui um pouco:

• iterools (lista) versão: 11.62 segundos

Acredito que a versão complicada das funções do gerador seja a mais rápida possível no Python. Mas não é realmente muito mais rápido que a versão reduzida, aproximadamente 4% mais rápido com base em minhas medidas.

Uma abordagem alternativa à resposta da agf:

def factors(n):    
    result = set()
    for i in range(1, int(n ** 0.5) + 1):
        div, mod = divmod(n, i)
        if mod == 0:
            result |= {i, div}
    return result

Aqui está uma alternativa à solução da @ agf, que implementa o mesmo algoritmo em um estilo mais pitônico:

def factors(n):
    return set(
        factor for i in range(1, int(n**0.5) + 1) if n % i == 0
        for factor in (i, n//i)
    )

Essa solução funciona no Python 2 e no Python 3 sem importações e é muito mais legível. Não testei o desempenho dessa abordagem, mas, assintoticamente, deve ser a mesma e, se o desempenho for uma preocupação séria, nenhuma das soluções será a ideal.

Existe um algoritmo de força de mercado no SymPy chamado factorint :

>>> from sympy import factorint
>>> factorint(2**70 + 3**80) 
{5: 2,
 41: 1,
 101: 1,
 181: 1,
 821: 1,
 1597: 1,
 5393: 1,
 27188665321L: 1,
 41030818561L: 1}

Isso levou menos de um minuto. Alterna entre um coquetel de métodos. Consulte a documentação vinculada acima.

Dados todos os fatores primos, todos os outros fatores podem ser construídos facilmente.

Observe que, mesmo que a resposta aceita tenha sido executada por tempo suficiente (ou seja, uma eternidade) para fatorar o número acima, para alguns números grandes ela falhará, como no exemplo a seguir. Isto é devido ao desleixado int(n**0.5). Por exemplo, quando n = 10000000000000079**2, temos

>>> int(n**0.5)
10000000000000078L

Como 10000000000000079 é primo , o algoritmo da resposta aceita nunca encontrará esse fator. Observe que não é apenas um desdobramento; para números maiores, será desativado por mais. Por esse motivo, é melhor evitar números de ponto flutuante em algoritmos desse tipo.

Para n até 10 ** 16 (talvez até um pouco mais), aqui está uma solução rápida e pura do Python 3.6,

from itertools import compress

def primes(n):
    """ Returns  a list of primes < n for n > 2 """
    sieve = bytearray([True]) * (n//2)
    for i in range(3,int(n**0.5)+1,2):
        if sieve[i//2]:
            sieve[i*i//2::i] = bytearray((n-i*i-1)//(2*i)+1)
    return [2,*compress(range(3,n,2), sieve[1:])]

def factorization(n):
    """ Returns a list of the prime factorization of n """
    pf = []
    for p in primeslist:
      if p*p > n : break
      count = 0
      while not n % p:
        n //= p
        count += 1
      if count > 0: pf.append((p, count))
    if n > 1: pf.append((n, 1))
    return pf

def divisors(n):
    """ Returns an unsorted list of the divisors of n """
    divs = [1]
    for p, e in factorization(n):
        divs += [x*p**k for k in range(1,e+1) for x in divs]
    return divs

n = 600851475143
primeslist = primes(int(n**0.5)+1) 
print(divisors(n))

Melhorias adicionais na solução da afg & eryksun. O seguinte trecho de código retorna uma lista classificada de todos os fatores sem alterar a complexidade assintótica do tempo de execução:

    def factors(n):    
        l1, l2 = [], []
        for i in range(1, int(n ** 0.5) + 1):
            q,r = n//i, n%i     # Alter: divmod() fn can be used.
            if r == 0:
                l1.append(i) 
                l2.append(q)    # q's obtained are decreasing.
        if l1[-1] == l2[-1]:    # To avoid duplication of the possible factor sqrt(n)
            l1.pop()
        l2.reverse()
        return l1 + l2

Idéia: Em vez de usar a função list.sort () para obter uma lista classificada, que oferece complexidade ao nlog (n); É muito mais rápido usar list.reverse () em l2, o que requer complexidade O (n). (É assim que o python é criado.) Após l2.reverse (), l2 pode ser anexado a l1 para obter a lista classificada de fatores.

Observe que l1 contém i -s que estão aumentando. l2 contém q -s que estão diminuindo. Essa é a razão por trás do uso da idéia acima.

Tentei a maioria dessas respostas maravilhosas com o tempo para comparar sua eficiência com a minha função simples e, no entanto, vejo constantemente as minhas superarem as listadas aqui. Eu pensei em compartilhar e ver o que vocês pensam.

def factors(n):
    results = set()
    for i in xrange(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            results.add(i)
            results.add(int(n/i))
    return results

Como está escrito, você precisará importar math para testar, mas substituir math.sqrt (n) por n **. 5 deve funcionar da mesma forma. Eu não me incomodo em perder tempo verificando duplicatas porque duplicatas não podem existir em um conjunto, independentemente.

Aqui está outra alternativa sem redução que funciona bem com grandes números. Ele usa sumpara achatar a lista.

def factors(n):
    return set(sum([[i, n//i] for i in xrange(1, int(n**0.5)+1) if not n%i], []))

Certifique-se de pegar o número maior que o sqrt(number_to_factor)de números incomuns como 99, que possui 3 * 3 * 11 e floor sqrt(99)+1 == 10.

import math

def factor(x):
  if x == 0 or x == 1:
    return None
  res = []
  for i in range(2,int(math.floor(math.sqrt(x)+1))):
    while x % i == 0:
      x /= i
      res.append(i)
  if x != 1: # Unusual numbers
    res.append(x)
  return res

A maneira mais simples de encontrar fatores de um número:

def factors(x):
    return [i for i in range(1,x+1) if x%i==0]

Aqui está um exemplo se você deseja usar o número dos números primos para ir muito mais rápido. Essas listas são fáceis de encontrar na internet. Eu adicionei comentários no código.

# http://primes.utm.edu/lists/small/10000.txt
# First 10000 primes

_PRIMES = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 
        31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 
        73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 
        127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 
        179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 
        233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 
        283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 
        353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 
        419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 
        467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 
        547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 
        607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 
        661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 
        739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 
        811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 
        877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 
        947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 
# Mising a lot of primes for the purpose of the example
)


from bisect import bisect_left as _bisect_left
from math import sqrt as _sqrt


def get_factors(n):
    assert isinstance(n, int), "n must be an integer."
    assert n > 0, "n must be greather than zero."
    limit = pow(_PRIMES[-1], 2)
    assert n <= limit, "n is greather then the limit of {0}".format(limit)
    result = set((1, n))
    root = int(_sqrt(n))
    primes = [t for t in get_primes_smaller_than(root + 1) if not n % t]
    result.update(primes)  # Add all the primes factors less or equal to root square
    for t in primes:
        result.update(get_factors(n/t))  # Add all the factors associted for the primes by using the same process
    return sorted(result)


def get_primes_smaller_than(n):
    return _PRIMES[:_bisect_left(_PRIMES, n)]

um algoritmo potencialmente mais eficiente do que os apresentados aqui já (especialmente se houver pequenos fatos concretos n). o truque aqui é ajustar o limite até o qual a divisão de teste é necessária toda vez que fatores primos são encontrados:

def factors(n):
    '''
    return prime factors and multiplicity of n
    n = p0^e0 * p1^e1 * ... * pk^ek encoded as
    res = [(p0, e0), (p1, e1), ..., (pk, ek)]
    '''

    res = []

    # get rid of all the factors of 2 using bit shifts
    mult = 0
    while not n & 1:
        mult += 1
        n >>= 1
    if mult != 0:
        res.append((2, mult))

    limit = round(sqrt(n))
    test_prime = 3
    while test_prime <= limit:
        mult = 0
        while n % test_prime == 0:
            mult += 1
            n //= test_prime
        if mult != 0:
            res.append((test_prime, mult))
            if n == 1:              # only useful if ek >= 3 (ek: multiplicity
                break               # of the last prime) 
            limit = round(sqrt(n))  # adjust the limit
        test_prime += 2             # will often not be prime...
    if n != 1:
        res.append((n, 1))
    return res

é claro que isso ainda é uma divisão experimental e nada mais sofisticado. e, portanto, ainda é muito limitado em sua eficiência (especialmente para grandes números sem divisores pequenos).

isso é python3; a divisão //deve ser a única coisa que você precisa para se adaptar ao python 2 (adicionar from __future__ import division).

Usar set(...)torna o código um pouco mais lento e só é realmente necessário quando você verifica a raiz quadrada. Aqui está a minha versão:

def factors(num):
    if (num == 1 or num == 0):
        return []
    f = [1]
    sq = int(math.sqrt(num))
    for i in range(2, sq):
        if num % i == 0:
            f.append(i)
            f.append(num/i)
    if sq > 1 and num % sq == 0:
        f.append(sq)
        if sq*sq != num:
            f.append(num/sq)
    return f

o if sq*sq != num: condição é necessária para números como 12, em que a raiz quadrada não é um número inteiro, mas o piso da raiz quadrada é um fator.

Observe que esta versão não retorna o número em si, mas é uma correção fácil, se você desejar. A saída também não está classificada.

Eu cronometrei a execução 10.000 vezes em todos os números de 1 a 200 e 100 vezes em todos os números de 1 a 5000. Ele supera todas as outras versões que testei, incluindo as soluções de dansalmo, Jason Schorn, oxrock, agf, steveha e eryksun, embora a oxrock seja de longe a mais próxima.

seu fator máximo não é mais que seu número, então, digamos

def factors(n):
    factors = []
    for i in range(1, n//2+1):
        if n % i == 0:
            factors.append (i)
    factors.append(n)

    return factors

voilá!

 import math

    '''
    I applied finding prime factorization to solve this. (Trial Division)
    It's not complicated
    '''


    def generate_factors(n):
        lower_bound_check = int(math.sqrt(n))  # determine lowest bound divisor range [16 = 4]
        factors = set()  # store factors
        for divisors in range(1, lower_bound_check + 1):  # loop [1 .. 4]
            if n % divisors == 0:
                factors.add(divisors)  # lower bound divisor is found 16 [ 1, 2, 4]
                factors.add(n // divisors)  # get upper divisor from lower [ 16 / 1 = 16, 16 / 2 = 8, 16 / 4 = 4]
        return factors  # [1, 2, 4, 8 16]


    print(generate_factors(12)) # {1, 2, 3, 4, 6, 12} -> pycharm output

 Pierre Vriens hopefully this makes more sense. this is an O(nlogn) solution. 

Use algo tão simples quanto a seguinte compreensão da lista, observando que não precisamos testar 1 e o número que estamos tentando encontrar:

def factors(n):
    return [x for x in range(2, n//2+1) if n%x == 0]

Em referência ao uso da raiz quadrada, digamos que queremos encontrar fatores de 10. A parte inteira do sqrt(10) = 4portantorange(1, int(sqrt(10))) = [1, 2, 3, 4] e o teste de até 4 claramente perdem 5.

A menos que esteja faltando algo que eu sugiro, se você deve fazer dessa maneira, usando int(ceil(sqrt(x))). É claro que isso produz muitas chamadas desnecessárias para funções.

Eu acho que para melhor legibilidade e velocidade a solução da oxrock é a melhor, então aqui está o código reescrito para o python 3+:

def num_factors(n):
    results = set()
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0: results.update([i,int(n/i)])
    return results

Fiquei bastante surpreso ao ver a pergunta de que ninguém usava numpy nem quando é muito mais rápido que os loops python. Ao implementar a solução da @ agf com numpy, resultou em média 8 vezes mais rápido . Acredito que se você implementasse algumas das outras soluções numpy, poderia obter momentos incríveis.

Aqui está a minha função:

import numpy as np
def b(n):
    r = np.arange(1, int(n ** 0.5) + 1)
    x = r[np.mod(n, r) == 0]
    return set(np.concatenate((x, n / x), axis=None))   

Observe que os números do eixo x não são a entrada para as funções. A entrada para as funções é 2 para o número no eixo x menos 1. Então, onde dez é a entrada, seria 2 ** 10-1 = 1023

import 'dart:math';
generateFactorsOfN(N){
  //determine lowest bound divisor range
  final lowerBoundCheck = sqrt(N).toInt();
  var factors = Set<int>(); //stores factors
  /**
   * Lets take 16:
   * 4 = sqrt(16)
   * start from 1 ...  4 inclusive
   * check mod 16 % 1 == 0?  set[1, (16 / 1)]
   * check mod 16 % 2 == 0?  set[1, (16 / 1) , 2 , (16 / 2)]
   * check mod 16 % 3 == 0?  set[1, (16 / 1) , 2 , (16 / 2)] -> unchanged
   * check mod 16 % 4 == 0?  set[1, (16 / 1) , 2 , (16 / 2), 4, (16 / 4)]
   *
   *  ******************* set is used to remove duplicate
   *  ******************* case 4 and (16 / 4) both equal to 4
   *  return factor set<int>.. this isn't ordered
   */

  for(var divisor = 1; divisor <= lowerBoundCheck; divisor++){
    if(N % divisor == 0){
      factors.add(divisor);
      factors.add(N ~/ divisor); // ~/ integer division 
    }
  }
  return factors;
}

Eu acho que essa é a maneira mais simples de fazer isso:

    x = 23

    i = 1
    while i <= x:
      if x % i == 0:
        print("factor: %s"% i)
      i += 1