Ich habe eine Python-Liste der Primfaktoren einer Zahl. Wie kann ich (pythonically) alle Faktoren finden?

Question

Ich arbeite an einem Projekt Euler Problem, das Faktorisierung einer ganzen Zahl erfordert. Ich kann mit einer Liste aller Primzahlen kommen, dass der Faktor einer bestimmten Zahl sind. Der Fundamentalsatz der Arithmetik bedeutet, dass ich diese Liste herzuleiten verwenden können alle Faktor der Anzahl.

Mein aktueller Plan ist jede Nummer in der Liste der Basis Primzahlen zu nehmen und seine Leistung zu erhöhen, bis es nicht mehr ein ganze Zahl Faktor ist die maximalen Exponenten für jede Primzahl zu finden. Dann werde ich jede mögliche Kombination von Prime-Exponent Paare multiplizieren.

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.

Als nächstes tun jede Kombination von diesen auf den maximalen Exponenten bis zu den 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 ist die Liste von 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 haben. Zwei Probleme: Erstens, ich glaube nicht, dass es überhaupt sehr Pythonic ist. Ich möchte, dass beheben. Zweitens, ich wirklich hat keinen Pythonic Weg, um den kombinatorischen zweiten Schritt zu tun. Aus Scham, habe ich dich aus dem lächerlichen Satz von Schleifen verschont.

n ist die Zahl, die wir zu Faktor wollen. listOfAllPrimes ist eine vorberechnete Liste der Primzahlen bis 10 Mio. Euro.

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

Statt einer Liste von Exponenten, betrachten Sie einfach Wiederholung jeder Primfaktor von der Anzahl, wie oft es is ein Faktor. Danach wird auf der resultierende primefactors Arbeitsliste-with-Wiederholungen, itertools.combinations tut genau das, was Sie brauchen - Sie müssen nur die Kombinationen von Länge 2 bis len(primefactors) - 1 Elemente enthalten erfordern (die Kombinationen von nur einer die Primfaktoren sind, dass alle von ihnen wird die Zahl wieder - wenn Sie wollen diejenigen, auch nur verwenden range(1, len(primefactors) + 1) anstelle des range(2, len(primefactors)), die mein Hauptvorschlag verwenden würde).

Es wird Wiederholungen in den Ergebnissen (zB 6 zweimal als Faktor der 12 erscheinen werden, da der primefactors des letzteren [2, 2, 3] sein wird), und sie können natürlich in den üblichen Verfahren werden ausgesondert (dh sorted(set(results)) zum Beispiel).

primefactors gegeben listOfAllPrimes, sollte zum Beispiel berechnen:

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 beginnen Sie Ihre Lösung aus der Menge der Primfaktoren? wenn Sie eine Nummer faktorisieren können Sie so bequem alle ihre Primfaktoren (Wiederholung) erhalten und von ihnen für jeden Faktor die Exponenten. In diesem Sinne kann man 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 und product sind hier nicht implementiert, aber Sie bekommen die Idee (beide sind ziemlich einfach zu schreiben)

IMHO, wobei mathematische Probleme können die Euler Probleme schön statt zwingend Stil mit Hilfe der funktionellen gelöst werden (obwohl ich zugeben, dass einige Lösungen nicht als pythonic kommen können je nach Wunsch).

Answer 3

könnten Sie itertools.combinations() alle möglichen Kombinationen von Faktoren zu erhalten sobald Sie Ihre Liste der wiederholten-Primzahlen, wie [2, 2, 3, 3, 5] für 180 bekommen. Dann einfach aus jeder Kombination der Komponenten multipliziert werden Sie einen Faktor erhalten.

Answer 4

Mit ein paar kühlere 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 es mehr machen „pythonic“, wenn Sie wollen, was immer das bedeutet.

Answer 6

Ein alles in einer Lösung; das heißt keine Notwendigkeit für eine bestehende Liste der wichtigsten Faktoren.

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

Hinweis: [1] : Als Primzahl-Generator können Sie einen von wählen Wie eine effiziente Umsetzung unendlichem Generator von Primzahlen in Python? oder eigene (zB Ihre listOfAllPrimes) verwenden.

Dies erzeugt eine vollständige Liste Faktor, das heißt einschließlich 1 und das number Argument selbst. Wenn Sie diese weglassen möchten, können Sie all_factors(number)[1:-1] verwenden.

$ 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])