Tengo una lista de Python de los factores primos de un número. ¿Cómo encuentro (pythonically) todos los factores?

Question

Estoy trabajando en un problema de Project Euler que requiere la factorización de un número entero. Puedo obtener una lista de todos los números primos que son el factor de un número dado. El teorema fundamental de la aritmética implica que puedo usar esta lista para derivar cada factor del número.

Mi plan actual es tomar cada número en la lista de primos de base y aumentar su potencia hasta que ya no sea un factor entero para encontrar los exponentes máximos para cada primo. Luego, multiplicaré todas las combinaciones posibles de pares de exponente principal.

Así, por ejemplo, de 180:

Given: prime factors of 180: [2, 3, 5] 
Find maximum exponent of each factor: 
    180/2^1 = 90 
    180/2^2 = 45 
    180/2^3 = 22.5 - not an integer, so 2 is the maximum exponent of 2. 

    180/3^1 = 60 
    180/3^2 = 20 
    180/3^3 = 6.6 - not an integer, so 2 is the maximum exponent of 3. 

    180/5^1 = 36 
    180/5^2 = 7.2 - not an integer, so 1 is the maximum exponent of 5. 

continuación, hacer todas las combinaciones de éstos hasta el máximo exponente para obtener los factores:

2^0 * 3^0 * 5^0 = 1 
    2^1 * 3^0 * 5^0 = 2 
    2^2 * 3^0 * 5^0 = 4 
    2^0 * 3^1 * 5^0 = 3 
    2^1 * 3^1 * 5^0 = 6 
    2^2 * 3^1 * 5^0 = 12 
    2^0 * 3^2 * 5^0 = 9 
    2^1 * 3^2 * 5^0 = 18 
    2^2 * 3^2 * 5^0 = 36 
    2^0 * 3^0 * 5^1 = 5 
    2^1 * 3^0 * 5^1 = 10 
    2^2 * 3^0 * 5^1 = 20 
    2^0 * 3^1 * 5^1 = 15 
    2^1 * 3^1 * 5^1 = 30 
    2^2 * 3^1 * 5^1 = 60 
    2^0 * 3^2 * 5^1 = 45 
    2^1 * 3^2 * 5^1 = 90 
    2^2 * 3^2 * 5^1 = 180 

Así que la lista de factores = [1 , 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 30, 36, 45, 60, 90, 180]

Aquí está el código que tengo hasta ahora. Dos problemas: Primero, no creo que sea muy pitónico. Me gustaría arreglar eso. En segundo lugar, I realmente no tengo una forma pitonica para hacer el segundo paso combinatorio. Por vergüenza, te evité el ridículo conjunto de bucles.

n es el número que queremos factorizar. listOfAllPrimes es una lista precalculada de los números primos de hasta 10 millones.

def getListOfFactors(n, listOfAllPrimes): 
    maxFactor = int(math.sqrt(n)) + 1 
    eligiblePrimes = filter(lambda x: x <= maxFactor, listOfAllPrimes) 
    listOfBasePrimes = filter(lambda x: n % x ==0, eligiblePrimes) 

    listOfExponents = [] #(do I have to do this?) 
    for x in listOfBasePrimes: 
     y = 1 
     while (x**(y+1)) % n == 0: 
      y += 1 
     listOfExponents.append(y) 

Answer 1

En lugar de una lista de exponentes, consideran simplemente repitiendo cada factor primordial por el número de veces que es un factor. Después de eso, trabajando en el resultado primefactors lista-with-repeticiones, itertools.combinations hace justo lo que necesita - sólo va a requerir las combinaciones de longitud de 2 a len(primefactors) - 1 partidas incluidas (las combinaciones de un solo son los factores primos, que de todos de ellos será el número original; si también los quiere, simplemente use range(1, len(primefactors) + 1) en lugar del range(2, len(primefactors)) que usaría mi sugerencia principal).

Habrá repeticiones en los resultados (por ejemplo, 6 aparecerán dos veces como un factor de 12, ya que de primefactors este último será [2, 2, 3]) y que por supuesto puede ser eliminada de la forma habitual (es decir sorted(set(results)) por ejemplo) .

Para calcular primefactors dado listOfAllPrimes, consideran por ejemplo:

def getprimefactors(n): 
    primefactors = [] 
    primeind = 0 
    p = listOfAllPrimes[primeind] 
    while p <= n: 
     if n % p == 0: 
      primefactors.append(p) 
      n //= p 
     else: 
      primeind += 1 
      p = listOfAllPrimes[primeind] 
    return primefactors 

Answer 2

Usted podría utilizar itertools.combinations() para obtener todas las combinaciones posibles de factores, una vez que ha llegado a su lista de números primos repetidas, tales como [2, 2, 3, 3, 5] para 180. Entonces, simplemente multiplicar los componentes de cada combinación te dará un factor.

Answer 3

Aquí es una solución simple y eficaz al problema original:

def getDivisors(n): 
    divisors = [] 
    d = 1 
    while d*d < n: 
     if n % d == 0: 
      divisors.append(d) 
      divisors.append(n/d); 
     d += 1 
    if d*d == n: 
     divisors.append(d) 
    return divisors 

La lista de salida es sin clasificar. Puedes hacerlo más "pitónico" si quieres, sea lo que sea que eso signifique.

Answer 4

¿Por qué comienzas la solución a partir del conjunto de factores principales? cuando factorizas un número, puedes obtener todos sus factores primos (repetidos) y, a partir de ellos, los exponentes de cada factor. Con esto en mente, puede escribir esto:

import itertools 
prime_factors = get_prime_factors(180) 
# 2, 2, 3, 3, 5 
factorization = [(f, len(list(fs))) for (f, fs) in itertools.groupby(prime_factors)] 
# [(2, 2), (3, 2), (5, 1)] 
values = [[(factor**e) for e in range(exp+1)] for (factor, exp) in factorization] 
# [[1, 2, 4], [1, 3, 9], [1, 5]] 
print sorted(product(xs) for xs in itertools.product(*values)) 
# [1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 30, 36, 45, 60, 90, 180] 

get_prime_factors y product no se aplican aquí, pero se entiende la idea (ambos son bastante simples para escribir)

en mi humilde opinión, siendo problemas matemáticos, la ecuación de Euler los problemas se pueden resolver muy bien utilizando un estilo funcional en lugar de imperativo (aunque reconozco que algunas soluciones pueden no ser tan pitónicas como se desee).

Answer 5

Con algunas características de Python más frías:

def factors(num): 
    for p in primes: 
     if num==1: break # stop when num is 1 
     while True: # these factors may be repeated 
      new, rest = divmod(num, p) # does div and mod at once 
      if rest==0: # its divisible 
       yield p # current prime is factor 
       num = new # continue with the div'd number 
      else: 
       break # no factor so break from the while 


print list(factors(2*2*3*3*5*7*11*11*13)) # [2, 2, 3, 3, 5, 7, 11, 11, 13] ofc 

Answer 6

Una solución todo en uno; es decir, no hay necesidad de una lista existente de los factores primos.

#!/usr/bin/python3 -O 

from primegen import erat3 as generate_primes # see Note[1] 
import operator as op, functools as ft, itertools as it 

def all_factors(number): 
    prime_powers= [] 

    for prime in generate_primes(): # for prime in listOfAllPrimes 
     if prime > number: break 

     this_prime_powers= [1] 
     new_number, modulo= divmod(number, prime) 

     while not modulo: 
      number= new_number 
      this_prime_powers.append(this_prime_powers[-1] * prime) 
      new_number, modulo= divmod(number, prime) 

     if len(this_prime_powers) > 1: 
      prime_powers.append(this_prime_powers) 

    # at this point: 
    # if number was 360, prime_powers is [[1, 2, 4, 8], [1, 3, 9], [1, 5]] 
    # if number was 210, prime_powers is [[1, 2], [1, 3], [1, 5], [1, 7]] 

    return sorted(
     ft.reduce(op.mul, combination, 1) 
     for combination in it.product(*prime_powers)) 

if __name__ == "__main__": 
    def num_result(number): 
     return number, all_factors(number) 
    print(num_result(360)) 
    print(num_result(210)) 
    print(num_result(7)) 

Nota [1]: Como generador de números primos, puede elegir uno de How to implement an efficient infinite generator of prime numbers in Python? o utilizar su propio (por ejemplo, su listOfAllPrimes).

Esto produce una lista de factores completa, es decir, que incluye 1 y el argumento number. Si desea omitir estos, puede usar all_factors(number)[1:-1].

$ allfactors.py 
(360, [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180, 360]) 
(210, [1, 2, 3, 5, 6, 7, 10, 14, 15, 21, 30, 35, 42, 70, 105, 210]) 
(7, [1, 7])