List all multiplicative partitions of n Given a positive number n, output all distinct multiplicative partitions of n in any convenient format.

A multiplicative partition of n is a set of integers, all greater than one, such that their product is n. For example, 20 has the following distinct multiplicative partitions:

2 * 2 * 5
2 * 10
4 * 5
20


Order does not matter, so 2 * 2 * 5 is the same partition as 2 * 5 * 2.



Examples:

1 -&gt; {}
2 -&gt; {2}
4 -&gt; {2, 2}, {4}
20 -&gt; {2, 2, 5}, {2, 10}, {4, 5}, {20}
84 -&gt; {2, 2, 3, 7}, {2, 2, 21}, {2, 14, 3}, {2, 6, 7}, {2, 42}, {4, 3, 7}, {28, 3}, {4, 21}, {6, 14}, {12, 7}, {84}
Brachylog, 16 bytes

&gt;~l:{1&lt;}a.*?,.=o


This is a function (not a full program) which takes a positive number as input and generates all multiplicative partitions of it. (I also avoided using any prime factorization builtins in this solution, mostly because I wasn't sure they'd help; I might try a more builtin-heavy solution too at some point.)

Try it online! (Extra code has been added around the function here to make it into a full program; if you provide the function shown above to TIO directly, it will run the function but not print its output anywhere, which is kind-of useless as a demonstration.)

This program really disappoints me, because much of it is working around bugs in the Brachylog interpreter and deficiencies in its specification, rather than actually solving the problem; but the interpreter is what it is. (Even with the program like this, the interpreter uses much more memory than it logically should, and crashes due to memory exhaustion, but luckily on small problems it manages to produce the desired output first.) In a hypothetical "perfect version of Brachylog" you could just write ~*.o.:{&gt;1}a,, which would be 4 bytes shorter, but I needed to add extra constraints to help the interpreter out a bit. (I don't really like Brachylog much, and would rather stick to Prolog, but it needed similar hints to make the program work and they're much longer to write. So Brachylog it is.)

Explanation:

As usual, a Brachylog program is a set of constraints; by default, the first constraint constrains the input against an unknown (which I'll call A), the second constraint constrains A against a second unknown B, and so on until we reach the output. Some characters, such as {}, can change this general flow, so I use a different set of letters (e.g. X/Y) to represent unknowns in nested predicates.

&gt;       A is smaller than the input
~l      B has length A
  1&lt;    X is 1, Y is larger
:{1&lt;}a  For each element X of B, it corresponds to an element Y of C
.       C, the output, and D are all identical
*       E is the product of D's elements
?       E, the input, and F are all identical
,       There's no constraint between F and G
.       G, the output, and H are all identical
=       H and I are identical, and need to be evaluated early
o       The output can be produced by sorting I


It's still unclear how the program works, so let's try simplifying the constraints a bit. C, D, G, H, and I are all the same (and equal to the output). E and F are also the same (and equal to the input). So our constraints boil down to this:


A is the length of B and of the output, and is smaller than the input.
B consists of all 1s, and isn't particularly useful (it's part of the program simply because in the existing Brachylog interpreter, :{1&lt;}a needs its left argument to have a constrained length, or else the interpreter goes into an infinite loop).
The output consists entirely of numbers greater than 1 (i.e. greater than the corresponding element of B).
The product of the elements of the output is equal to the input.
The output is unchanged by sorting it (i.e. is in sorted order).


Incidentally, I didn't explicitly specify that all the elements of the output are integers, something which might seem to be required; however, Brachylog's constraint solver can't handle non-integers, so it'll conveniently produce only the solutions that involve integers.

Clearly, "the length of the output is smaller than the input" is going to be true whenever the output is a multiplicative partition of the input (because 2x > x for all nonnegative x, i.e. positive 2x). So we can disregard that constraint; it's only there to give the Brachylog interpreter a working strategy for evaluating the program. The other constraints (that the output is sorted, that its product is the input, and that its elements are all greater than 1) are the definition of a multiplicative partition, and therefore this function is basically just a direct implementation of the question.