打印给定数字的所有因素的独特组合

Question

打印正整数因子的所有唯一组合的最有效算法是什么.例如,如果给定的数字是24,那么输出应该是

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

这里注意到当打印6*4时,不打印4*6.所以基本上这是一个在不考虑顺序的情况下获取唯一子集的问题(查看问题的一种方法).但目标是拥有一个运行速度最快的函数,因此将因子存储在数据结构中以进行进一步操作可能会消耗更多时间.我已经尝试了我的算法并在下面粘贴了我的代码,但它似乎没有给我想要的结果,我在递归调用中犯了一些错误.你能帮我找出一个有效的方法吗？

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 1

试试这种递归方法，它也接受 2 个以上的输入，即一个字符串，用于在 for 循环中结转 i 的当前值以执行后续缩减，还有一个临时 int 以了解何时不打印重复的反转，即 8*3 和 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) 调用此方法，
如果您发现此方法存在缺陷，请告诉我。谢谢！

Answer 2

1) 如果i < num和i > num/2，则num % i == num - i。（很容易证明。）所以你的for循环将毫无意义地检查所有大于的整数，num/2并且该if语句只会成功一次，temp == 2. 我不认为那是你想要的。

2）在你解决这个问题时，递归可能需要产生很多答案。但你只打印temp *一次。所以输出看起来会有点奇怪。

3)isprime没有必要。num只要您遵循以下几点，无论它是否是素数，它始终是一个合法的因子。

4）最后，您需要弄清楚如何避免多次打印相同的因式分解。简单的解决方案是仅产生因子单调非递增的分解（如您的示例中所示）。为了做到这一点，递归需要产生具有某个最大因子（这将是先前发现的因子）的因式分解。因此，递归函数应该（至少）有两个参数：因子数和最大允许因子​​。（您还需要处理我在第 4 点中指出的问题。）

下面的Python代码确实（我相信）解决了这个问题，但它仍然做了很多不必要的划分。与 Python 风格不同的是，它打印每个分解而不是充当生成器，因为这样更容易翻译成 Java。

# Uses the last value in accum as the maximum factor; a cleaner solution
# would have been to pass max_factor as an argument.
def factors(number, accum=[]):
  if number == 1:
    print '*'.join(map(str, accum))
  else:
    if accum:
      max_factor = min(accum[-1], number)
    else:
      max_factor = number
    for trial_factor in range(max_factor, 1, -1):
      remnant = number / trial_factor
      if remnant * trial_factor == number:
        factors(remnant, accum + [trial_factor,])

可以优化该for语句。例如，一旦计算remnant，您就知道下一个必须至少大一个，因此当较小时remnant您可以跳过一堆trial_factor值。remnant