找到单号是彼此最接近

40-> 5 * 8（未10 * 4）

两个最高的因素35-> 7 * 5 等

我猜是这样的：

candidate = input.square_root.round_to_nearest_int; 
while (true){ 
test = input/candidate; 
if (test.is_integer) return; 
else 
candidate.decrement; 
}

来源

2016-11-20 Tel

你给出的想法是自然而明确的作品。这不是非常有效，因为它符合天真的分解分解法。更好的方法可能是首先将数字完全分解（使用比试划更复杂的东西），然后找到最均衡的方法将这些因素分成两组。 –

我想我所问的是以平方根开始的起点。但是，它是启发式和低效率的;我只会输入最低值为几千的值。 – Tel

你的方法做的工作。

如果n = ab然后a <= sqrt(n) <= b，因此如果a,b被选择为使得b-a被最小化，由此得出a是小于或等于所述平方根的n最大除数。我对你的伪代码进行的唯一调整是检查余数，看它是否为零，而不是检查商是否是整数。喜欢的东西（在Python）：

import math 

def closestDivisors(n): 
    a = round(math.sqrt(n)) 
    while n%a > 0: a -= 1 
    return a,n//a

例如，

>>> closestDivisors(36) 
(6, 6) 
>>> closestDivisors(40) 
(5, 8) 
>>> closestDivisors(1000003) 
(1, 1000003)

（自最近一次输入是素数）。

来源

2016-11-20 04:32:47

谢谢，所以我的直觉是正确的 - 我只是无法表达它（最小化两个因素之间的差异是对问题的优雅描述）。 – Tel

找到单号是彼此最接近

回答

相关问题