algorithm - 计算 N 个因子的可能组合，不包括 1 和它本身，乘法产生 N

Question

给定一个数 N，找出它的因数(不包括 1 和 N)的组合数，乘法得到 N。例如:

N = 12
answer = 3
relevant factors : 2,3,4,6
combinations : {2,6},{3,4},{2,2,3}.

为了解决这个问题，我提出了以下逻辑，它适用于几乎所有情况，但在少数情况下会低估。请帮助我理解我所缺少的。我的逻辑:

我将这组组合分为“主要”和“次要”。作为因素的直接组合出现的那些是主要的。在上面的示例中，{2,6} 和 {3,4} 是主要的。那些因进一步打破原有因素之一而出现的是次要的。例如:{2,2,3} 可以称为 2 的组合，6 分解为 {2,3} 或 3 的组合，4 分解为 {2,2}。对于每个数字，我首先找到主要因素的数量，然后通过递归重复最大相关因素的过程来找到次要因素的数量。例如:

f(32) = 2 + f(16);
f(16) = 2 + f(8);
f(8) = 1 + f(4);
f(4) = 1;
Thus, f(32) = 6.

在上面，32 的主要组合是 {2,16} 和 {4,8}。因此第一步中的 2。这也解释了其余步骤。

问题是，对于 N 的几个值，此解决方案失败。例如:对于 90，它返回 8，但正确答案是 10。对于 180，它返回 16，但正确答案是 25。对于 60，正确答案是10，但我的是 9。

请帮帮我。

Answer 1

使用来自@kcsquared 的评论的指导，我能够理解如何解决这个问题。

我们只需要遍历 n 的所有约数。这样做会给出我在问题中提到的“主要组合”。为了使用递归找到乘法分区，我应该递归地找到正在进行的迭代中找到的两个除数中较大者的除数，但这次进行了修改。与其从 2 开始搜索，不如从迭代中较小的除数开始。这是为了防止过度计数。下面是我的代码。

def divisors(s,l):
    tot = 0
    for i in range(s,l):
        if n%i == 0 and n//i >= i: #Preventing counting same combo again, and early stopping.
            tot += 1
            if n//i > 0:
                tot += divisors(i,n//i)
    return tot
n = 60
print(divisors(2,n))

这是给出正确答案。我之前提出的实现要复杂得多，并且除了最大的因素之外无法递归。如果我对 n = 60 这样做，我将无法计算 {3,4,5}，因为:

On partitioning 60, I get: 2,3,4,5,6,10,12,15,20,30.

现在，如果我进一步除以 30，然后除以 15，然后除以 5，我将不会得到 4，因为 4 不是其中任何一个的因数。因此，4 只会在第一步中被计算一次，作为 {4,15} 的一部分，但永远不会作为 {3,4,5}。

使用新方法，我还可以除以 20 (20*3 = 60)，这将计算 3 以及 4 和 5 的出现次数。