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

numeros primos python while

Question

¿Puede alguien explicarme una forma 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 lleva demasiado tiempo ejecutar un resultado para un gran número.

Answer 1

Aquí hay otra alternativa sin reducir que funciona bien con números grandes. Utiliza 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], []))

Answer 2

Aquí hay un ejemplo si desea usar 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)]

Answer 3

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 importar 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 una preocupación seria, ninguna solución es óptima.

Answer 4

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

Answer 5

Creo que para la legibilidad y la velocidad, la solución de @ 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

Answer 6

Esta es mi solución al problema:

Tenga en cuenta que esto llevará más tiempo para números más grandes. El único problema es que solo sé cómo programar en Python 3.x. Creo que lo único que necesita cambiar es input () a raw_input ().

# Sets the number
num = int(input("Enter number to be tested."))

for i in range(1,num): # Tests all numbers from 1 to the num
    while (num % i) == 0: '''''' If the remainder of the number when it is divided by i is 0''''''
        print(i) # Prints i
        break # Stops it from repeating one number infinitely
else: # After the previous process if done, do this
    print("Finished") # Says that the process is finished

input ("Press return/enter to close the program") '''''' Closes the program after pressing enter''''''

Answer 7

Existe un algoritmo de fuerza industrial en SymPy 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. Ver la documentación vinculada arriba.

Dado todos los factores primos, todos los otros factores se pueden construir fácilmente.

Tenga en cuenta que incluso si se permitió 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 descuidado int(n**0.5) . Por ejemplo, cuando n = 10000000000000079**2 , tenemos

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

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

Answer 8

He intentado la mayoría de estas maravillosas respuestas con tiempo para comparar su eficacia con mi simple función y, sin embargo, constantemente 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 matemática para probar, pero reemplazar math.sqrt (n) con n **. 5 debería funcionar igual de bien. No me molesto en perder el tiempo buscando duplicados porque los duplicados no pueden existir en un conjunto de todos modos.

Answer 9

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 permitir que Python lo compilara, luego lo ejecuté bajo el comando de tiempo (1) tres veces y mantuve el mejor tiempo.

• reducir versión: 11.58 segundos
• versión de itertools: 11.49 segundos
• Versión engañosa: 11.12 segundos

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

• versión de iterools (lista): 11.62 segundos

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

Answer 10

La solución presentada por @agf es excelente, pero se puede lograr un tiempo de ejecución ~ 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 extraños, no es necesario verificarlos cuando se trata de números impares.

Acabo de empezar a resolver acertijos Project Euler yo mismo. En algunos problemas, se llama una comprobación de divisor dentro de dos bucles anidados, y el rendimiento de esta función es por lo tanto esencial.

Combinando este hecho con la excelente solución de agf, terminé 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.

Ejecuté algunas pruebas para verificar la velocidad. Debajo está el código usado. Para producir las diferentes parcelas, 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)

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

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

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

X = rango (1,100,000,1001) (paridad alterna)

Answer 11

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 le da complejidad a nlog (n); Es mucho más rápido usar list.reverse () en l2 que toma O (n) complejidad. (Así es como se hace python.) Después de l2.reverse (), l2 se puede agregar a l1 para obtener la lista ordenada de factores.

Observe, 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.

Answer 12

Para n hasta 10 ** 16 (tal vez incluso un poco más), aquí hay una solución Python 3.6 pura y rápida,

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

Answer 13

Sin usar la función reducir () que no está incorporada en Python3:

def factors(n):
    return list(sorted(set([f(x) for x in range(1, int(n**0.5) + 1) if not n % x 
                for f in (lambda x: x, lambda x: n // x)])))

Answer 14

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

Answer 15

Usar el set(...) hace que el código sea un poco más lento, y solo es realmente necesario para cuando se consulta 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é corriendo 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 oxrock es, con mucho, el más cercano.

Answer 16

Use algo tan simple como la siguiente lista de comprensión, señalando 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 raíz cuadrada, digamos que queremos encontrar factores de 10. La porción entera del sqrt(10) = 4 por lo tanto range(1, int(sqrt(10))) = [1, 2, 3, 4] y probando hasta 4 claramente falla 5.

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

Answer 17

un algoritmo potencialmente más eficiente que los presentados aquí ya (especialmente si hay pequeños factores primarios en n ). el truco aquí es ajustar el límite hasta donde 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, una división de prueba y nada más elegante. y por lo tanto aún muy limitado en su eficiencia (especialmente para grandes números sin divisores pequeños).

esto es python3; la división // debería ser lo único que necesita adaptar para python 2 (agregar from __future__ import division ).

Answer 18

from functools import reduce

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

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

¿Por qué la raíz cuadrada es el límite superior?

sqrt(x) * sqrt(x) = x . Entonces, si los dos factores son iguales, ambos son la raíz cuadrada. Si haces un factor más grande, tienes que hacer que el otro factor sea más pequeño. 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 puede usar x / fac1 para obtener fac2 .

La reduce(list.__add__, ...) está tomando las listas pequeñas 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 resto al dividir n entre el más pequeño es cero (No es necesario que compruebe el más grande también, simplemente lo consigue dividiendo n por el más pequeño).

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

Answer 19

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)))
if __name__ == "__main__":
       n = int(input("enter the number to get factors"))
       fact = list(factors(n))
       for x in fact:
              print(x)