Ich arbeite an einem Project Euler-Problem, bei dem eine ganze Zahl zerlegt werden muss. Ich kann eine Liste aller Primzahlen erstellen, die der Faktor einer bestimmten Zahl sind. Der Grundsatz der Arithmetik impliziert, dass ich diese Liste verwenden kann, um @ abzuleitjede Faktor der Zahl.

ein aktueller Plan ist es, jede Zahl in der Liste der Basisprimzahlen zu nehmen und ihre Potenz zu erhöhen, bis es kein ganzzahliger Faktor mehr ist, um die maximalen Exponenten für jede Primzahl zu finden. Dann multipliziere ich jede mögliche Kombination von Prim-Exponenten-Paaren.

So 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.

Nächste, mache jede Kombination von diesen bis zum maximalen Exponenten, 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

So 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 bisher habe. Zwei Probleme: Erstens denke ich, dass es überhaupt nicht sehr pythonisch ist. Ich möchte das beheben. Zweitens, ichJa wirklic haben keine pythonische Möglichkeit, den kombinatorischen zweiten Schritt durchzuführen. Aus Scham habe ich dich von den lächerlichen Schleifen verschont.

n ist die Zahl, die wir ausrechnen 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)