6
$\begingroup$

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.

  • 2
    Hint: Suppose $n=p_1^{r_1}p_2^{r_2} ... p_k^{r_k}$ - you need to pick a power of $p_1$ between 0 and $r_1$ ...2012-08-23
  • 2
    Already for $p^n$ the problem is difficult! We are then looking for the *partitions* of $n$ (see Wikipedia).2012-08-23
  • 0
    @MarkBennet - I'm not getting the hint. Can you please expound a bit, either in a comment or an answer?2012-08-24

2 Answers 2