将一个数字考虑在大致相同的因素中

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]