将数字分解为大致相等的因子

Question

我想把一个数分解成一个大小尽可能接近的数元组，其乘积就是初始数。输入是我们想要的因子数和所需因子数。

对于双因子情况（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\u I-x\u avg）或∑（x\u I-x\u avg）^2或其他类似的东西。

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

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

编辑：我更愿意最小化这些因素的总和。仍然对上述内容感兴趣，但如果有人有一个想法，可以同时计算出最佳的m值，这样因子之和就最小了，那就太好了！




Answer 1

这个怎么样，对于m=3和一些n：

1. 取n的最大因子，小于n的立方根，称之为f1

对于336，比336的立方根小的最大因子是6（我认为）。将336除以6得到56（另一个因子，想想吧！）对56执行相同的数学运算并寻找两个因子，我们得到7和8。

请注意，对于小于3个因子的任何数字都不起作用。此方法可以扩展为m

如果这是正确的，并且我不是太疯狂，那么解决方案将是递归函数：

factors=[]
n=336
m=3

def getFactors(howMany, value):
  if howMany < 2:
    return value

  root=getRoot(howMany, value) # get the root of value, eg square root, cube, etc.
  factor=getLargestFactor(value, root) # get the largest factor of value smaller than root
  otherFactors=getFactors(howMany-1, value / factor)
  otherFactors.insert(factor)
  return otherFactors
print getFactors(n, m)

我懒得编写其余的代码，但应该可以了。

Answer 2

您可以从相同的原则开始：查找小于或等于m的数字作为因数。然后可以递归查找其余的因子。

def get_factors(n, m):
    factors = []
    factor = int(n**(1.0/m) + .1) # fudged to deal with precision problem with float roots
    while n % factor != 0:
        factor = factor - 1
    factors.append(factor)
    if m > 1:
        factors = factors + get_factors(n / factor, m - 1)
    return factors

print get_factors(729, 3)

Answer 3

要回答第二个问题（它使因子之和最小化），最好将数字拆分为素数。事实上，对于除4以外的任何正复合数，其素数因子之和都小于该数本身，因此任何具有复合数的拆分都可以通过将该复合数拆分为其素数因子来改进。

为了回答您的第一个问题，其他人建议的贪婪方法不会奏效，正如我在评论中指出的那样，贪婪会立即提取8作为第一个因素，然后将剩余的数字拆分为3、9、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]