Eu tenho uma lista Python dos principais fatores de um número. Como encontro (pythonically) todos os fatores?
Estou trabalhando em um problema do Project Euler que requer a fatoração de um número inteiro. Posso apresentar uma lista de todos os números primos que são o fator de um determinado número. O Teorema Fundamental da Aritmética implica que eu possa usar esta lista para derivarcada fator do número.
Meu plano atual é pegar cada número na lista de números primos de base e aumentar sua potência até que não seja mais um fator inteiro para encontrar o máximo de expoentes para cada número primo. Então, multiplicarei todas as combinações possíveis de pares de expoentes primos.
Então, por exemplo, para 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.
Em seguida, faça todas as combinações até o expoente máximo para obter os fatores:
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
Portanto, a lista de fatores = [1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 30, 36, 45, 60, 90, 180]
Aqui está o código que tenho até agora. Dois problemas: primeiro, não acho que seja muito pitonico. Eu gostaria de consertar isso. Segundo eurealmente não tem uma maneira pitônica de executar o segundo passo combinatório. Por vergonha, eu poupou você do conjunto ridículo de loops.
n é o número que queremos fatorar. listOfAllPrimes é uma lista pré-calculada dos números primos de até 10 milhões.
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)