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

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.

我意识到数字 "close to each other in size" 的含义存在一些歧义。我不介意这是否被解释为最小化 Σ(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=3 和一些 n:

求n小于n的立方根的最大因数，称之为f1
将n除以f1，称之为g
找到 g 的 "roughly equal factors"，如 m=2 示例。

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

请注意，这不适用于因数少于 3 个的任何数字。这个方法可以扩展为m > 3，maybe.

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

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

要回答您的第二个问题（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]

Answer 4

m=5 n=4 then m^(1/n)

你得到：

Answer=1.495

然后

1.495*1.495*1.495*1.495 = 5

在 C# 中

double Result = Math.Pow(m,1/(double)n);

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

Factoring a number into roughly equal factors

python

algorithm

math