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

Question

Estoy trabajando en un proyecto de Euler problema que requiere la factorización de un entero. Puedo llegar a 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 utilizar esta lista para derivar todos los factores de la serie.

Mi plan actual es tomar cada número en la lista de números primos base y aumentar su potencia hasta que ya no es un factor entero para encontrar los exponentes máximos para cada primo. A continuación, voy a multiplicar todas las combinaciones posibles de pares de prime-exponente.

Así, por ejemplo, para 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.

A 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í la lista de factores = [1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 30, 36, 45, 60, 90, 180]

Este es el código que tengo hasta ahora. Dos problemas: En primer lugar, no creo que es muy Pythonic en absoluto. Me gustaría arreglar eso. En segundo lugar, realmente no tienen una forma Pythonic para hacer el segundo paso combinatorio. Por vergüenza, te he librado de la ridícula conjunto de bucles.

n es el número que queremos factor. listOfAllPrimes es una lista previamente calculado de los números primos hasta 10 millones de dólares.

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, considere simplemente repitiendo cada factor primordial por el número de veces que es un factor. Después de eso, trabajando en el primefactors resultante lista-con-repeticiones, itertools.combinations hace exactamente lo que necesita - usted sólo necesita las combinaciones de longitud de 2 a artículos len(primefactors) - 1 incluidos (las combinaciones de un solo son los factores primos, que de todos ellos será el número original - si quieres aquellos también, sólo tiene que utilizar en lugar de la range(1, len(primefactors) + 1) range(2, len(primefactors)) la que usaría mi principal sugerencia).

Habrá repeticiones en los resultados (por ejemplo, 6 aparecerán dos veces como un factor de 12, ya primefactors de 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, tenga en cuenta, 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

¿Por qué comenzar su solución desde el conjunto de factores primos? cuando factorizar un número que puede conseguir tan fácilmente todos sus factores primos (repetido) y de ellos los exponentes de cada factor. Con esto en mente, puede escribir lo siguiente:

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 simple de escritura)

En mi humilde opinión, siendo problemas matemáticos, los problemas de Euler se puede resolver utilizando bien funcional en lugar de estilo imperativo (aunque reconozco que algunas soluciones pueden no salir como Pythonic según se desee).

Answer 3

itertools.combinations() para obtener todas las combinaciones posibles de factores una vez que haya conseguido su lista de números primos repetidas, como [2, 2, 3, 3, 5] para 180. Luego, basta con multiplicar los componentes de cada combinación le conseguirá un factor.

Answer 4

Con unos pocos refrigerador cuenta con Python:

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 5

He aquí una sencilla y eficaz solución 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. Puede que sea más "Pythonic" si se quiere, sea lo que sea.

Answer 6

Una solución todo en uno; es decir, sin 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 Cómo implementar un eficiente generador infinito de números primos en Python? o utilizar su propio (por ejemplo, su listOfAllPrimes).

Esto produce una lista de factores completo, es decir incluyendo 1 y el propio argumento number. Si desea omitir estos, se puede utilizar 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])