Find all ways to factor a number

Question

An example of what I'm looking for will probably explain the question best. 24 can be written as:

• 12 · 2
• 6 · 2 · 2
• 3 · 2 · 2 · 2
• 8 · 3
• 4 · 2 · 3
• 6 · 4

I'm familiar with finding all the prime factors of a number ($24 = 3 · 2^3$), as well as all the factor pairs (24 = 12·2, 8·3, 6·4). I'm assuming one or both will form the basis of the answer, but I can't figure out an algorithm to find all the possible ways to represent a number as a product of 2 or more other numbers. So, what is a (preferably efficient) way to accomplish this?

Note: this is not homework, it's just for my own knowledge.

Answer 1

That's called multiplicative partitions, and there is a generating function discovered by Oppenheim and McMahon. You could use it. The list of the number of multiplicative partitions is on http://oeis.org/A001055

Answer 2

Well if you have the prime factorization for a number (let's use your example of 24), then any combination of its prime factors must be a factor. $$24 = 3\times 2^3$$ So any combination of {3, 2, 2, 2} is a factor. The way you go about taking all subsets of a set in an efficient manner is more of a CS problem.

But just to drive home the point:

{{3}=2, {3, 2}=6, {3,2,2}=12,{3,2,2,2}=24, {2}=2, {2,2}=4, {2,2,2}=8}

And then remember 1.