找到單號是彼此最接近

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

找到單號是彼此最接近

回答

相關問題