Ich habe eine Python-Liste mit den Primfaktoren einer Zahl. Wie kann ich (in Python) alle Faktoren finden?

Question

Ich arbeite an einem Projekt-Euler-Problem, das die Faktorisierung einer ganzen Zahl erfordert. Ich kann eine Liste mit allen Primzahlen erstellen, die ein Faktor einer bestimmten Zahl sind. Der Fundamentalsatz der Arithmetik besagt, dass ich diese Liste verwenden kann, um Folgendes abzuleiten jede Faktor der Zahl.

Mein derzeitiger Plan ist, jede Zahl in der Liste der Primzahlen zu nehmen und ihre Potenz zu erhöhen, bis sie kein ganzzahliger Faktor mehr ist, um die maximalen Exponenten für jede Primzahl zu finden. Dann werde ich jede mögliche Kombination von Primzahl-Exponent-Paaren multiplizieren.

Also zum Beispiel für 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.

Als Nächstes wird jede Kombination bis zum maximalen Exponenten durchgeführt, um die Faktoren zu erhalten:

    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

Also die Liste der Faktoren = [1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 30, 36, 45, 60, 90, 180]

Hier ist der Code, den ich bis jetzt habe. Zwei Probleme: Erstens finde ich, dass er überhaupt nicht sehr Pythonisch ist. Das würde ich gerne beheben. Zweitens, ich wirklich haben keine pythonische Methode, um den zweiten kombinatorischen Schritt auszuführen. Aus Scham erspare ich Ihnen die lächerliche Menge von Schleifen.

n ist die Zahl, die wir faktorisieren wollen. listOfAllPrimes ist eine vorberechnete Liste der Primzahlen bis zu 10 Millionen.

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

Eine Komplettlösung, d.h. eine Liste der Primfaktoren ist nicht erforderlich.

#!/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))

Anmerkung[1] : Als Primzahlgenerator können Sie eine der folgenden Zahlen auswählen Wie implementiert man einen effizienten unendlichen Generator für Primzahlen in Python? oder verwenden Sie Ihre eigenen (z. B. Ihre listOfAllPrimes ).

Dies ergibt eine vollständige Faktorliste, d. h. einschließlich 1 und die number Argument selbst. Wenn Sie diese weglassen wollen, können Sie 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])