algorithm - How to find multiplicative partitions of any integer?

Question

I'm looking for an efficient algorithm for computing the multiplicative partitions for any given integer. For example, the number of such partitions for 12 is 4, which are

12 = 12 x 1 = 4 x 3 = 2 x 2 x 3 = 2 x 6

I've read the wikipedia article for this, but that doesn't really give me an algorithm for generating the partitions (it only talks about the number of such partitions, and to be honest, even that is not very clear to me!).

The problem I'm looking at requires me to compute multiplicative partitions for very large numbers (> 1 billion), so I was trying to come up with a dynamic programming approach for it (so that finding all possible partitions for a smaller number can be re-used when that smaller number is itself a factor of a bigger number), but so far, I don't know where to begin!

Any ideas/hints would be appreciated - this is not a homework problem, merely something I'm trying to solve because it seems so interesting!

Answer 1

The first thing I would do is get the prime factorization of the number.

From there, I can make a permutation of each subset of the factors, multiplied by the remaining factors at that iteration.

So if you take a number like 24, you get

2 * 2 * 2 * 3 // prime factorization
a   b   c   d
// round 1
2 * (2 * 2 * 3) a * bcd
2 * (2 * 2 * 3) b * acd (removed for being dup)
2 * (2 * 2 * 3) c * abd (removed for being dup)
3 * (2 * 2 * 2) d * abc

Repeat for all "rounds" (round being the number of factors in the first number of the multiplication), removing duplicates as they come up.

So you end up with something like

// assume we have the prime factorization 
// and a partition set to add to
for(int i = 1; i < factors.size; i++) {
    for(List<int> subset : factors.permutate(2)) {
        List<int> otherSubset = factors.copy().remove(subset);
        int subsetTotal = 1;
        for(int p : subset) subsetTotal *= p;
        int otherSubsetTotal = 1;
        for(int p : otherSubset) otherSubsetTotal *= p;
        // assume your partition excludes if it's a duplicate
        partition.add(new FactorSet(subsetTotal,otherSubsetTotal));
    }
}