算法：对一个整数X进行因式分解，得到尽可能多的不同的正整数（Y1…Yk），使（Y1+1）（Y2+1）…（Yk+1）=X

Question

我最近在打开.kattis.com. 这个问题的链接是https://open.kattis.com/problems/listgame2。 基本上，这是一个问题，要求玩家对一个整数X（10^3<；=X<；=10^15）进行因式分解，以得到尽可能多的不同的正整数（Y₁，…，Y_k），这样（Y₁+1）（Y₂+1）⋯（Y_k+1）=X

我已经想出了一个使用Python3的解决方案，它确实通过了几个测试用例，但其中一个失败了：MyStatus

我的代码是：

def minFactor(n, start):
    maxFactor = round(n**0.5)
    for i in range(start, maxFactor+1):
        if n % i == 0:
            return i
    return n

def distinctFactors(n):
    curMaxFactor = 1
    factors = []

    while n > 1:
        curMaxFactor = minFactor(n, curMaxFactor+1)
        n //= curMaxFactor
        factors.append(curMaxFactor)

    # This is for the situation where the given number is the square of a prime number
    # For example, when the input is 4, the returned factors would be [2,2] instead of [4]
    # The if statement below are used to fix this flaw
    # And since the question only requires the length of the result, deleting the last factor when repeat do works in my opinion
    if factors[-1] in factors[:-1]:
        del factors[-1]

    return factors

num = int(input())
print(len(distinctFactors(num)))

具体来说，我在上面代码中的想法非常简单。例如，当给定的输入是36时，我运行minFactor函数来发现36的最小因子是2（在本例中忽略1）。然后，我通过36/2得到18，并调用minFactor（18,3），因为2不再是不同的了，所以我开始寻找最小因子18乘以3。显然是3，所以我通过在函数distinctFactors中做18/3得到6，并调用minFactor（6，4），因为4小于sqrt（6）或6**0.5，所以会返回6本身，最后得到列表因子为[2,3,6]，这是正确的。在

我仔细研究了我的代码和算法好几个小时了，但我还是搞不懂为什么我的测试失败了，有人能帮我解决我的困境吗？？？正在等待答复。在

Answer 1

考虑数字2**6.11**5。在

您的算法将找到5个因素：

2
2**2
2**3
11
11**2
(11**2 this will be discarded as it is a repeat)

6个长度的答案是：

^{pr2}$