Print all unique combination of factors of a given number

crazyim5 picture crazyim5 · Feb 27, 2013 · Viewed 9.6k times · Source

What is the most efficient algorithm to print all unique combinations of factors of a positive integer. For example if the given number is 24 then the output should be

24*1
12*2
8*3
6*4
6*2*2
4*3*2
3*2*2*2

Here notice that when 6*4 gets printed then 4*6 doesn't get printed. So basically it's a problem of taking unique subsets without considering the order (one way to look at the problem). But the objective is to have a function that runs the fastest, so storing the factors in a data structure to do further manipulation might consume more time. I have tried my algorithm and pasted my code below, but it doesn't seem to give me the desired result, I'm making some mistake in my recursive call. Can you help me figure out an efficient way to do this?

public static void printfact(int num){
        int temp=0;
        for(int i=num-1;i>=num/2;i--){
            if(num % i == 0){
                temp = num/i;
                System.out.println(temp + " * " + i);
                if(isprime(i)==false){
                    System.out.print(temp + " * ");
                    printfact(i);
                }
            }
        }
}

Answer

crazyim5 picture crazyim5 · Feb 28, 2013

Try this recursive approach that also takes in 2 more inputs namely a string to carry over the current value of i in for loop to perform subsequent reduction and also a temp int to know when not to print duplicate reversals i.e., 8*3 and 3*8.

public static void printFactors(int number, String parentFactors, int parentVal) {
    int newVal = parentVal;
    for (int i = number - 1; i >= 2; i--) {

        if (number % i == 0) {
            if (newVal > i) {
                newVal = i;
            }
            if (number / i <= parentVal && i <= parentVal
                    && number / i <= i) {
                System.out.println(parentFactors + i + "*" + number / i);
                newVal = number / i;
            }

            if (i <= parentVal) {
                printFactors(number / i, parentFactors + i + "*", newVal);
            }
        }

    }

}

And call this method using printFactors(12,'',12)
Let me know if you find flaws in this approach. Thanks!