¿Cuál es la forma más eficiente de encontrar todos los factores de un número en Python?

¿Puede alguien explicarme una manera eficiente de encontrar todos los factores de un número en Python (2.7)?

Puedo crear algoritmos para hacer este trabajo, pero creo que está mal codificado y toma mucho tiempo ejecutar un resultado para un gran 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))) 

Esto devolverá todos los factores, muy rápidamente, de un número n .

¿Por qué raíz cuadrada como límite superior?

sqrt(x) * sqrt(x) = x . Entonces, si los dos factores son iguales, ambos son la raíz cuadrada. Si aumentas un factor, debes reducir el otro factor. Esto significa que uno de los dos siempre será menor o igual que sqrt(x) , por lo que solo tiene que buscar hasta ese punto para encontrar uno de los dos factores coincidentes. Luego puedes usar x / fac1 para obtener fac2 .

La reduce(list.__add__, ...) está tomando las pequeñas listas de [fac1, fac2] y uniéndolas en una larga lista.

El [i, n/i] for i in range(1, int(sqrt(n)) + 1) if n % i == 0 devuelve un par de factores si el rest cuando se divide n por el más pequeño es cero (No es necesario que compruebe el más grande también; solo se obtiene al dividir n por el más pequeño).

El set(...) en el exterior es deshacerse de los duplicados, lo que solo ocurre con los cuadrados perfectos. Para n = 4 , esto devolverá 2 dos veces, así que el set se deshace de uno de ellos.

La solución presentada por @agf es excelente, pero se puede lograr un tiempo de ejecución de ~ 50% más rápido para un número impar arbitrario al verificar la paridad. Como los factores de un número impar siempre son impares, no es necesario verificarlos cuando se trata de números impares.

Acabo de empezar a resolver los acertijos de Project Euler . En algunos problemas, una verificación de divisor se llama dentro de dos ciclos nesteds for bucles, y el rendimiento de esta función es esencial.

Combinando este hecho con la excelente solución de agf, he terminado con esta función:

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

Sin embargo, en números pequeños (~ <100), la sobrecarga adicional de esta alteración puede hacer que la función tarde más tiempo.

Realicé algunas pruebas para comprobar la velocidad. A continuación se muestra el código utilizado. Para producir las diferentes plots, modifiqué el X = range(1,100,1) consecuencia.

 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 = rango (1,100,1) X = rango (1,100,1)

No hay diferencia significativa aquí, pero con números más grandes, la ventaja es obvia:

X = rango (1,100000,1000) (solo números impares) X = rango (1,100000,1000) (solo números impares)

X = rango (2,100000,100) (solo números pares) X = rango (2,100000,100) (solo números pares)

X = rango (1,100000,1001) (paridad alterna) X = rango (1,100000,1001) (paridad alterna)

La respuesta de AGF es realmente genial. Quería ver si podía reescribirlo para evitar el uso de reduce() . Esto es lo que se me ocurrió:

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

También probé una versión que usa funciones de generador difíciles:

 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) 

Lo cronometré computando:

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

Lo ejecuté una vez para que Python lo comstackra, luego lo ejecuté bajo el comando time (1) tres veces y mantuve el mejor momento.

  • reducir versión: 11.58 segundos
  • Versión de itertools: 11.49 segundos.
  • Versión complicada: 11,12 segundos.

Tenga en cuenta que la versión de itertools está creando una tupla y pasándola a flatten_iter (). Si cambio el código para construir una lista en su lugar, se ralentiza ligeramente:

  • Versión de iterools (lista): 11.62 segundos.

Creo que la versión de las funciones del generador complicado es la más rápida posible en Python. Pero en realidad no es mucho más rápido que la versión reducida, aproximadamente un 4% más rápido según mis mediciones.

Un enfoque alternativo a la respuesta de 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 

Mejora adicional a la solución de afg & eryksun. El siguiente fragmento de código devuelve una lista ordenada de todos los factores sin cambiar la complejidad asintótica del tiempo de ejecución:

  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 

Idea: en lugar de usar la función list.sort () para obtener una lista ordenada que da complejidad a nlog (n); Es mucho más rápido usar list.reverse () en l2, que requiere O (n) complejidad. (Así es como se hace python). Después de l2.reverse (), l2 puede agregarse a l1 para obtener la lista ordenada de factores.

Aviso, l1 contiene i -s que están aumentando. l2 contiene q -s que están disminuyendo. Esa es la razón detrás de usar la idea anterior.

He intentado la mayoría de estas maravillosas respuestas con el tiempo para comparar su eficiencia en comparación con mi simple función y, sin embargo, veo que las mías superan a las que se enumeran aquí. Pensé que lo compartiría y vería lo que todos piensan.

 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, tendrá que importar math para probar, pero reemplazar math.sqrt (n) con n **. 5 debería funcionar igual de bien. No me molesto en perder tiempo buscando duplicados porque los duplicados no pueden existir en un conjunto independientemente.

Para n hasta 10 ** 16 (quizás incluso un poco más), aquí hay una solución rápida y pura de 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((ni*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)) 

Aquí hay una alternativa a la solución de @agf que implementa el mismo algoritmo en un estilo más pythonic:

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

Esta solución funciona tanto en Python 2 como en Python 3 sin importaciones y es mucho más legible. No he probado el rendimiento de este enfoque, pero asintóticamente debería ser el mismo, y si el rendimiento es un problema grave, ninguna solución es óptima.

Aquí hay otra alternativa sin reducción que funciona bien con grandes números. Utiliza la sum para aplanar la lista.

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

Asegúrese de tomar el número más grande que sqrt(number_to_factor) para números inusuales como 99, que tiene 3 * 3 * 11 y 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 

En SymPy hay un algoritmo de gran potencia en la industria llamado 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} 

Esto tomó menos de un minuto. Cambia entre un cóctel de métodos. Consulte la documentación vinculada anteriormente.

Dados todos los factores primos, todos los demás factores pueden construirse fácilmente.


Tenga en cuenta que incluso si se permitiera que la respuesta aceptada se ejecutara durante el tiempo suficiente (es decir, una eternidad) para factorizar el número anterior, para algunos números grandes fallará, como en el siguiente ejemplo. Esto se debe a la int(n**0.5) . Por ejemplo, cuando n = 10000000000000079**2 , tenemos

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

Dado que 10000000000000079 es primo , el algoritmo de la respuesta aceptada nunca encontrará este factor. Tenga en cuenta que no es solo un off-by-one; para números más grandes estará apagado por más Por esta razón, es mejor evitar los números de punto flotante en los algoritmos de este tipo.

Este es un ejemplo si desea utilizar el número de primos para ir mucho más rápido. Estas listas son fáciles de encontrar en internet. Agregué comentarios en el 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)] 

un algoritmo potencialmente más eficiente que los que se presentan aquí ya (especialmente si hay pequeños factores primarios en n ). El truco aquí es ajustar el límite según el cual se necesita la división de prueba cada vez que se encuentran factores primos:

 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 

Esto es, por supuesto, todavía la división de prueba y nada más sofisticado. y por lo tanto, todavía muy limitada en su eficiencia (especialmente para grandes números sin pequeños divisores).

esto es python3; la división // debe ser la única cosa que necesita adaptar para python 2 (agregue from __future__ import division ).

El uso de set(...) hace que el código sea un poco más lento, y solo es realmente necesario cuando se comprueba la raíz cuadrada. Aquí está mi versión:

 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 

La condición if sq*sq != num: es necesaria para números como 12, donde la raíz cuadrada no es un número entero, pero el piso de la raíz cuadrada es un factor.

Tenga en cuenta que esta versión no devuelve el número en sí, pero es una solución fácil si lo desea. La salida tampoco está ordenada.

Lo cronometré ejecutando 10000 veces en todos los números 1-200 y 100 veces en todos los números 1-5000. Supera a todas las otras versiones que probé, incluidas las soluciones de dansalmo, Jason Schorn, oxrock, agf, steveha y eryksun, aunque la de oxrock es la más cercana.

Use algo tan simple como la siguiente lista de comprensión, teniendo en cuenta que no necesitamos probar 1 y el número que estamos tratando de encontrar:

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

En referencia al uso de la raíz cuadrada, digamos que queremos encontrar factores de 10. La parte entera de sqrt(10) = 4 por lo tanto, range(1, int(sqrt(10))) = [1, 2, 3, 4] y probando hasta 4 fallos claramente 5.

A menos que me esté faltando algo que sugeriría, si debe hacerlo de esta manera, use int(ceil(sqrt(x))) . Por supuesto, esto produce muchas llamadas innecesarias a las funciones.

tu factor máximo no es más que tu número, entonces, 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á!

Creo que para la legibilidad y la solución de Speed ​​@ oxrock es la mejor, así que aquí está el código reescrito para 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 

Me sorprendió bastante cuando vi esta pregunta que nadie usaba el adormecimiento, incluso cuando el adormecimiento es mucho más rápido que los bucles de python. Al implementar la solución de @ agf con numpy, resultó en un promedio de 8 veces más rápido . Creo que si implementas algunas de las otras soluciones en Númpy, podrías obtener tiempos increíbles.

Aquí está mi función:

 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 los números del eje x no son la entrada a las funciones. La entrada a las funciones es 2 al número en el eje x menos 1. Entonces, donde diez es la entrada sería 2 ** 10-1 = 1023

Resultados de las pruebas de rendimiento del uso de numpy en lugar de bucles.

 import 'dart:math'; generateFactorsOfN(N){ //determine lowest bound divisor range final lowerBoundCheck = sqrt(N).toInt(); var factors = Set(); //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.. 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; } 
  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. 

Sin usar la función reduce () que no es una función incorporada en Python3:

 def factors(n): res = [f(x) for f in (lambda x: x, lambda x: n // x) for x in range(1, int(n**0.5) + 1) if not n % x] return set(res) # returns a set to remove the duplicates from res 

Considero que esta es la forma más sencilla de hacerlo:

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