Python中的Coprime因式分解

我必須編寫一個代碼來查找輸入數字10^num的兩個最高共素因子。Python中的Coprime因式分解

現在，我已經寫了：

def coprimes(num): 
    for x in range (2, num): 
     for y in range (2, num): 
      while (gcd(x,y) == 1) & (x != y): 
       if (x*y==num): 
        return (x,y)

這顯然是因爲forloops的很慢的程序。每當我將它輸入到終端時，它的速度都太慢而無法提供答案。我也不確定這是否正確。你有什麼建議可以改進這種方法嗎？

這種方法的一個例子的答案應該是：

>>> coprimes(10) 
(9765625, 1024)

來源

2013-09-29 user2827356

從哪個意義上說，一對互質因子最高？ – user2357112

以及9765625和1024應該是10的因子？ – user2357112

我認爲你的意思是'和'，而不是'＆'。 – iCodez

你想

return 2**num, 5**num

注意的問題是不明確的 - 它不是明確2**num, 5**num是否應被視爲高於1, 10**num。但是，這些因素對比其他任何因素都要高。

要得出這個答案，請注意，至多有一個因子可以被2整除，至多有一個因子可以被5整除。如果一個因子可以被2和5整除，另一個因子可以被2整除必須是1，任何整數都是互質爲1.如果一個因子可以被2整除，另一個因子整除5，我們可以選擇2和5的最高冪。（選項2或5除以兩個數字都不會產生更低的因子。）

來源

2013-09-29 21:08:30 user2357112

Python中的Coprime因式分解

回答

相關問題