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

Anstelle einer Liste von Exponenten kann man auch einfach Wiederholung jeder Primfaktor durch die Anzahl der Male, die er ist ein Faktor. Danach wird die Arbeit an den resultierenden primefactors Liste-mit-Wiederholungen, itertools.kombinationen tut genau das, was Sie brauchen - Sie benötigen nur die Kombinationen der Länge 2 bis len(primefactors) - 1 enthalten (die Kombinationen von nur einem sind die Primfaktoren, die von allen die ursprüngliche Zahl sind -- wenn Sie auch diese wollen, verwenden Sie einfach range(1, len(primefactors) + 1) anstelle der range(2, len(primefactors)) die mein Hauptvorschlag verwenden würde).

Es wird Wiederholungen in den Ergebnissen geben (z.B., 6 erscheint zweimal als Faktor von 12 da die letzteren primefactors wird sein [2, 2, 3] ) und sie können natürlich auf die übliche Art und Weise aussortiert werden (d.h. sorted(set(results)) zum Beispiel).

Zum Berechnen primefactors gegeben listOfAllPrimes zum Beispiel:

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

Warum geht man bei der Lösung von der Menge der Primfaktoren aus? Wenn man eine Zahl faktorisiert, kann man genauso gut alle ihre Primfaktoren (wiederholt) und daraus die Exponenten für jeden Faktor ermitteln. Mit diesem Gedanken im Hinterkopf, können Sie dies schreiben:

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 と product sind hier nicht implementiert, aber Sie verstehen die Idee (beide sind ziemlich einfach zu schreiben)

Da es sich bei den Euler-Problemen um mathematische Probleme handelt, lassen sie sich IMHO gut mit funktionalen statt mit imperativen Methoden lösen (auch wenn ich zugeben muss, dass einige Lösungen vielleicht nicht so pythonisch ausfallen wie gewünscht).

Answer 3

Sie könnten verwenden itertools.combinations() um alle möglichen Kombinationen von Faktoren zu erhalten, sobald Sie die Liste der Primzahlwiederholungen erhalten haben, z. B. [2, 2, 3, 3, 5] für 180 . Multipliziert man dann einfach die Komponenten jeder Kombination, erhält man einen Faktor.

Answer 4

Mit ein paar cooleren Python-Funktionen:

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

Hier ist eine einfache und effiziente Lösung für das ursprüngliche Problem:

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

Die Ausgabeliste ist unsortiert. Sie können sie "pythonischer" machen, wenn Sie wollen, was auch immer das bedeutet.