У меня есть список Python из главных факторов числа. Как мне (пиготически) найти все факторы?
-
30-09-2019 - |
Вопрос
Я работаю над проектной проблемой Эйлера, которая требует факторизации целого числа. Я могу придумать список всех простых чисел, которые являются фактором данного числа. Фундаментальная теорема арифметики подразумевает, что я могу использовать этот список для получения каждый фактор числа.
Мой нынешний план состоит в том, чтобы взять каждое число в списке базовых простых чисел и поднять его мощность до тех пор, пока он больше не будет целочисленным фактором, чтобы найти максимальные показатели для каждого премьера. Тогда я умножу все возможные комбинации парпрентских пар.
Так, например, для 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.
Далее делайте каждое сочетание из них до максимального показателя, чтобы получить факторы:
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
Так что список факторов = [1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 30, 36, 45, 60, 90, 180
Вот код у меня до сих пор. Две проблемы: Во-первых, я не думаю, что это очень питон вообще. Я хотел бы это исправить. Во-вторых, я В самом деле У вас нет питонового пути, чтобы сделать комбинаторный второй шаг. Из стыда я пощадил вас от смешного набора петель.
N - номер, который мы хотим фактически. ListoFallPrime - это предварительно продуманный список простых чисел до 10 миллионов.
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)
Решение
Вместо списка показателей, считайте просто повторение каждый главный фактор по количеству раз это является фактор. После этого, работая над результатом primefactors
списка с повторениями, Itertools.comБация делает только то, что вам нужно - вы просто потребуете комбинации длины 2 до len(primefactors) - 1
Товары включены (комбинации только одного являются основными факторами, все из них станут исходным числом - если вы тоже хотите, просто используйте range(1, len(primefactors) + 1)
вместо range(2, len(primefactors))
который будет использовать мое главное предложение).
В результатах будут повторы (например, 6
будет появляться в два раза в качестве фактора 12
, так как последний primefactors
будет [2, 2, 3]
) и, конечно, могут быть извлечены в обычные способы (т.е. sorted(set(results))
Например).
Вычислить primefactors
дано listOfAllPrimes
, Рассмотрим, например:
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
Другие советы
Почему вы начинаете свое решение от набора главных факторов? Когда вы активизируете номер, вы можете так же легко получить все свои основные факторы (повторные) и из них показатели для каждого фактора. С этим в виду, вы можете написать это:
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
не реализованы здесь, но вы получаете идею (оба довольно просты для записи)
ИМХО, будучи математическими проблемами, проблемы Эйлера могут быть хорошо решены с использованием функционала вместо императивного стиля (хотя я признаю, что некоторые решения могут не выйти как желаемое для питонов).
Вы могли бы использовать itertools.combinations()
Чтобы получить все возможные комбинации факторов, как только вы получили свой список повторных простых чисел, такие как [2, 2, 3, 3, 5]
для 180
. Отказ Затем просто умножение компонентов из каждой комбинации получит вам фактор.
С несколькими охлаждающими функциями Python:
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
Вот простое и эффективное решение первоначальной проблемы:
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
Выходной список несортирован. Вы можете сделать его более «Pythonic», если хотите, все, что значит.
Все в одном решении; Т.е. нет необходимости в существующем списке главных факторов.
#!/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))
Примечание [1: Как генератор простого номера, вы можете выбрать один из Как реализовать эффективный бесконечный генератор простых чисел в Python? или используйте свой собственный (например, ваш listOfAllPrimes
).
Это производит полный факторный список, то есть в том числе 1
и то number
сам аргумент. Если вы хотите опустить их, вы можете использовать all_factors(number)[1:-1]
.
$ 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])