打印给定数字的所有唯一因子组合 [英] Print all unique combination of factors of a given number

问题描述

打印正整数因子的所有唯一组合的最有效算法是什么？例如，如果给定的数字是24，则输出应为

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

请注意，当打印6 * 4时，则不会打印4 * 6。因此，基本上，这是一个不考虑顺序就采用唯一子集的问题（一种查看问题的方式）。但目标是拥有一个运行速度最快的功能，因此将因素存储在数据结构中以进行进一步操作可能会花费更多时间。我已经尝试过算法，并在下面粘贴了我的代码，但似乎并没有达到预期的效果，我在递归调用中犯了一些错误。您能帮我找出有效的方法吗？

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

推荐答案

尝试这种递归方法，该方法也需要2个以上的输入，即用于继承i in for循环中的当前值的字符串以执行后续的约简操作，以及一个临时int来了解何时不打印重复项反转，即8 * 3和3 * 8。

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

    }

}

并使用printFactors（12，''，12）

调用此方法。如果您发现此方法有缺陷，请告诉我。谢谢！

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

这篇关于打印给定数字的所有唯一因子组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！