python - 将一个数分解成大致相等的因子

Question

我想将一个数字分解成一个数字元组，这些数字的大小尽可能接近，其乘积是初始数字。输入是我们要因式分解的数量 n 和所需因数的数量 m。

对于双因子情况 (m==2)，寻找小于平方根的最大因子就足够了，所以我可以这样做

def get_factors(n):
  i = int(n**0.5 + 0.5)
  while n % i != 0:
    i -= 1
  return i, n/i

所以用 120 调用它会导致 10,12。

我意识到对于数字“大小彼此接近”的含义存在一些歧义。我不介意这是否被解释为最小化 Σ(x_i - x_avg) 或 Σ(x_i - x_avg)^2 或其他类似的东西。

对于 m==3 的情况，我希望 336 产生 6,7,8 和 729 生成 9,9,9。

理想情况下，我想要一个通用 m 的解决方案，但如果有人甚至对 m==3 也有想法，我将不胜感激。我也欢迎一般启发式方法。

编辑:我宁愿最小化这些因素的总和。仍然对上述内容感兴趣，但如果有人想出一种方法来计算最佳 m 值，使因子之和最小，那就太好了!

Answer 1

要回答您的第二个问题(m 最小化因子之和)，将数字拆分为其质因子始终是最佳选择。实际上，对于除 4 之外的任何正合数它的质因数之和小于数字本身，因此任何具有合数的拆分都可以通过将合数拆分为其质因数来改进。

要回答您的第一个问题，正如我在评论中指出的那样，其他人建议的贪婪方法是行不通的 4104打破他们，贪婪会立即提取8作为第一个因素，然后将剩余的数字强制拆分为[3, 9, 19] ，未能找到更好的解决方案[6, 6, 6, 19] .然而，一个简单的 DP 可以找到最佳解决方案。 DP的状态就是我们要分解的个数，我们要得到多少个因子，DP的值就是可能的最好和。类似于下面的代码。它可以通过更智能地进行因式分解来优化。

n = int(raw_input())
left = int(raw_input())


memo = {}
def dp(n, left): # returns tuple (cost, [factors])
    if (n, left) in memo: return memo[(n, left)]

    if left == 1:
        return (n, [n])

    i = 2
    best = n
    bestTuple = [n]
    while i * i <= n:
        if n % i == 0:
            rem = dp(n / i, left - 1)
            if rem[0] + i < best:
                best = rem[0] + i
                bestTuple = [i] + rem[1]
        i += 1

    memo[(n, left)] = (best, bestTuple)
    return memo[(n, left)]


print dp(n, left)[1]

例如

[In] 4104
[In] 4 
[Out] [6, 6, 6, 19]