Generating all factors of a number given its prime factorization

Question

If you already have the prime factorization of a number, what is the easiest way to get the set of all factors of that number? I know I could just loop from 2 to sqrt(n) and find all divisible numbers, but that seems inefficient since we already have the prime factorization.

I imagine it's basically a modified version of a combinations/choose function, but all I can seem to find is methods for counting the number of combinations, and ways of counting the number of factors, not to actually generate the combinations / factors.

Answer 1

Imagine prime divisors are balls in a bucket. If, for example, prime divisors of your number are 2, 2, 2, 3 and 7, then you can take 0, 1, 2 or 3 instances of 'ball 2'. Similarly, you can take 'ball 3' 0 or 1 times and 'ball 7' 0 or 1 times.

Now, if you take 'ball 2' twice and 'ball 7' once, you get divisor 2*2*7 = 28. Similarly, if you take no balls, you get divisor 1 and if you take all balls you get divisor 2*2*2*3*7 which equals to number itself.

And at last, to get all possible combinations of balls you can take from the bucket, you could easily use recursion.

void findFactors(int[] primeDivisors, int[] multiplicity, int currentDivisor, long currentResult) {
    if (currentDivisor == primeDivisors.length) {
        // no more balls
        System.out.println(currentResult);
        return;
    }
    // how many times will we take current divisor?
    // we have to try all options
    for (int i = 0; i <= multiplicity[currentDivisor]; ++i) {
        findFactors(primeDivisors, multiplicity, currentDivisor + 1, currentResult);
        currentResult *= primeDivisors[currentDivisor];
    }
}

Now you can run it on above example:

findFactors(new int[] {2, 3, 7}, new int[] {3, 1, 1}, 0, 1);