Ich habe eine Python-Liste der Primfaktoren einer Zahl. Wie finde ich (pythonisch) alle Faktoren?

Question

Ich arbeite an einem Projekt Euler-Problem, das die Faktorisierung einer ganzen Zahl erfordert. Ich kann eine Liste aller Primzahlen erstellen, die der Faktor einer gegebenen Zahl sind. Der Fundamentalsatz der Arithmetik besagt, dass ich diese Liste verwenden kann, um den Faktor Faktor abzuleiten.

Mein aktueller Plan ist es, jede Zahl in die Liste der Basis-Primzahlen aufzunehmen und ihre Potenz zu erhöhen, bis sie nicht länger ein ganzzahliger Faktor ist, um die maximalen Exponenten für jede Prim zu finden. Dann werde ich jede mögliche Kombination von Primzahl-Exponenten-Paaren 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. 

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 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 glaube ich nicht, dass es sehr pythonisch ist. Ich würde das gerne reparieren. Zweitens habe ich wirklich haben keine pythonische Art, den kombinatorischen zweiten Schritt zu tun. Aus Scham habe ich dich von den lächerlichen Loops verschont.

n ist die Zahl, die wir berücksichtigen möchten. 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

Statt einer Liste von Exponenten, betrachten einfach jeden Primfaktor von der Anzahl, wie oft es ist Wiederholung eines Faktor. Danach funktioniert die Arbeit an der resultierenden primefactors Liste-mit-Wiederholungen, itertools.combinations genau das, was Sie brauchen - Sie benötigen nur die Kombinationen von Länge 2 bis len(primefactors) - 1 Elemente enthalten (die Kombinationen von nur einem sind die wichtigsten Faktoren, das von allen von ihnen wird die ursprüngliche Zahl sein - wenn Sie jene auch wollen, verwenden Sie einfach range(1, len(primefactors) + 1) anstelle der range(2, len(primefactors)), die mein Hauptvorschlag verwenden würde).

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

primefactorslistOfAllPrimes gegeben zu berechnen, betrachten 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

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

Answer 3

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 unsortiert ist. Sie können es mehr "pythonisch" machen, wenn Sie wollen, was auch immer das bedeutet.

Answer 4

Warum beginnen Sie Ihre Lösung aus der Menge der Primfaktoren? Wenn Sie eine Zahl faktorisieren, können Sie leicht alle Primfaktoren (wiederholt) und daraus die Exponenten für jeden Faktor erhalten. 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, mathematische Probleme zu sein, die Euler Probleme können mit funktionalem statt imperativem Stil gelöst werden (obwohl ich anerkenne, dass einige Lösungen nicht als Python erscheinen, wie gewünscht).

Answer 5

Mit wenigen Kühlen Python Eigenschaften:

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 6

Eines alles in einer Lösung; d.h. keine Notwendigkeit für eine existierende Liste der Primfaktoren.

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

Note [1]: Als Primzahl Generator, können Sie eine aus How to implement an efficient infinite generator of prime numbers in Python? wählen oder eigene verwenden (zum Beispiel Ihre listOfAllPrimes).

Dies erzeugt eine vollständige Faktorliste, d. H. 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])