Ввести произвольное натуральное число, не превосходящее 1000000000, и вывести (через «*») все его разложения на натуральные сомножители, превосходящие 1, без учёта перестановок. Сомножители в каждом разложении и сами разложения (как последовательности) при выводе должны быть упорядочены по возрастанию. Само число также считается разложением. Можно использовать рекурсию.
24
Очевидно, единственное разложение простого числа — это само простое число.
2*2*2*3 2*2*6 2*3*4 2*12 3*8 4*6 24
Заметим, что в этом выводе каждое следующее разложение лексикографически «больше» предыдущего, например, 2*3*4 < 2*12, потому что (2, 3, 4) < (2, 12)
Спойлер:
Рекурсивная функция будет перебирать все делители d текущего N, не меньшие уже найденных (actually, последнего найденного; это гарантирует лексикографический порядок), и вызовет себя с параметрами «N/d, найденные_делители + d»; если N простое и не меньше последнего делителя — разложение найдено, функция выводит очередной список_делителей + N. Важный момент: у N не больше одного делителя, превосходящего $$ \sqrt(N)$$ , и в нашем алгоритме такой делитель всегда последний.