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.
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);