Поиск всех возможных разложений числа на множители

[AXR]

Добрый день!
Решаю задачу, в которой в одном из действий нужно найти ВСЕ возможные разложения числа 120 на целые множители (т.е. не только на простые).
Например,
120 = 30*4 - одно возможное разложение.
Но 30 = 15*2, т.е. 120 = 15*2*4 - второе возможное разложение.
Но 4 = 2*2, т.е. 15*2*2*2 - третье возможное разложение.
Я пытался пользоваться следущим алгоритмом: сначала ищем все делители числа 120: 1,2,3,4,5,6,8,10,12,15,20,24,30,40,60,120, затем делители этих делителей и т.д., но этот алгоритм слишком громоздкий и в нем легко запутаться. Может быть кто-нибудь знает другие способы нахождения таких разложений? И вообще, можно ли оценить, сколько всего вариантов таких разложений будет?
Заранее спасибо.

[worm2]

Попробуйте так:

Разложить(число N, мин.делитель M): список разложений
  Результат = список, состоящий из одного разложения N = [N];
  Цикл по всем A, делящим N, A >= M, A <= кв. корня из N:
    Промежуточный список K = Разложить(число/A, A)
    Цикл по всем разложениям k из K
      Добавить в Результат разложение [A, элементы разложения k]
    Конец цикла
  Конец цикла
Конец

[xolms]

Разложите число на простые $A=p_1^{a_1}*...*p_n^{a_n}$ А затем таблица, всех вариантов.
Сам не заметил, что хрень написал. Извините, вот правильно:$((a_1+1)*...*(a_n+1))/2$
Да...и как я мог так.

[Brukvalub]

xolms писал(а):

Разложите число на простые $A=p_1^{a_1}*...*p_n^{a_n}$ А затем таблица, всех вариантов.
А всего разложений- $((p_1+1)^{a_1}*...*(p_n+1)^{a_n})/2$

Мне кажется что число разложений найдено неверно. Например, для числа 169 я нашёл только два различных разложения на натуральные сомножители, и 4 - на целые, а по Вашей формуле их должно быть, как минимум, 98 штук?

[AXR]

Спасибо всем за помощь!
Извиняюсь за неточность в вопросе - множители должны быть натуральными числами.
У меня получилось 20 возможных комбинаций (без повторений). Вот таблица (серым отмечены повторяющиеся разложения):

[ИСН]

Если число in question является, скажем, n-й степенью простого, то искомое количество разложений равно числу неупорядоченных разбиений n, для которого простой формулы нет.
Из этого заключаю, что нет её и выше (в общем случае, т.е. для n любого вида).
Ну а уж как перебирать - дело вкуса. Я бы шёл от разложения на простые и делал бы примерно так:

перебор по кол-ву сомножителей (от 2 до скольки можно){
  перебор способов распределения p1 между сомножителями{
    перебор способов распределения p2...{
      ...
    }
  }
}

... чёрт, тоже сложно как-то выходит...

[bot]

xolms в сообщении #49360 писал(а):

Разложите число на простые $A=p_1^{a_1}*...*p_n^{a_n}$ А затем таблица, всех вариантов.
Сам не заметил, что хрень написал. Извините, вот правильно:$((a_1+1)*...*(a_n+1))/2$

Сочуствую, но опять не заметили ... Для 169 и 4 теперь одинаково вариантов получится, но по полтора.
Множество разбиений можно частично упорядочить естественным образом - порядок даже решёточным получится, но перечислять элементы этой решётки или даже посчитать их число не так просто. Для последнего можно попробовать рекуррентность написать (возможно она в комбинаторике Холла есть), но толку с неё мало будет.

[maxal]

см.
topic9585.html
http://mathworld.wolfram.com/UnorderedF ... ation.html
A001055

[Maslov]

(Оффтоп)

Я так понимаю, это в рамках разбора завалов дискуссия возобновилась? А то через три года как-то немного странно выглядит

[romanz]

Эта задача эквивалентна задачи подсчета всех разбиений мультиножества на подмультимножества и пока в общем случае не решена.