Хотя я видел сообщения о поиске простых множителей и делителей, я не нашел ответа на свой вопрос о факторизации в Python. У меня есть список простых множителей, т.е. для 24
это [2,2,2,3]
. Я хочу из этого списка все возможные факторизации, то есть для 24
вывод должен быть [[2,12], [3,8], [4,6], [2,2,6], [2,3,4], [2,2,2,3]]
. Я попробовал подходы itertool, но это создало много повторяющихся ответов и забыло другие (например, найти [2,3,4]
, но игнорировать [4,6]
).
Меня особенно интересует подход, использующий сгенерированный список основных факторов. Я нашел обходной путь с рекурсивной функцией.
def factors(n, n_list):
for i in range(2, 1 + int(n ** .5)):
if n % i == 0:
n_list.append([i, n // i])
if n // i not in primes: #primes is a list containing prime numbers
for items in factors(n // i, []):
n_list.append(sorted([i] + items))
fac_list = [[n]] #[n] has to be added manually
for facs in n_list: #removes double entries
if facs not in fac_list:
fac_list.append(facs)
return fac_list
Но для больших n это занимает много времени, так как приходится просматривать все числа, а не только простые числа. Комбинаторный подход для списка простых множителей должен быть намного быстрее.
Изменить. После просмотра нескольких ресурсов лучшим объяснением хорошей стратегии является ответ с наивысшим рейтингом здесь на SO. Краткий и простой в реализации на любом языке, который вы предпочитаете. Дело закрыто.
{}
для форматирования кода. - person Mr. T   schedule 08.12.2017