高效檢查兩個數字是否是共素數（相對素數）？

什麼是最有效的（「pythonic」）方式來測試/檢查兩個數字是共質數（相對於素數）在Python。高效檢查兩個數字是否是共素數（相對素數）？

目前我有這樣的代碼：

def gcd(a, b): 
    while b != 0: 
     a, b = b, a % b 
    return a 

def coprime(a, b): 
    return gcd(a, b) == 1 

print(coprime(14,15)) #Should be true 
print(coprime(14,28)) #Should be false

可以檢查/測試，如果兩個數值都比較素被認爲是「Python化」或者有一些更好的方法的代碼？

來源

2016-09-24 Chichi

看起來不錯。 – khelwood

你當然可以使用'math.gcd'，這是一個包含電池，應該更高性能。 –

注意：'math.gcd'在Python3.5中是新的，之前是'fractions.gcd'。 – mkiever

改進的唯一建議可能是您的功能gcd。也就是說，您可以使用math（Python 3.5）中定義的gcd來提高速度。

定義coprime2使用的gcd內置的版本：

from math import gcd as bltin_gcd 

def coprime2(a, b): 
    return bltin_gcd(a, b) == 1

你幾乎減少執行速度減半由於事實math.gcd在C實現（see math_gcd in mathmodule.c）：

%timeit coprime(14, 15) 
1000000 loops, best of 3: 907 ns per loop 

%timeit coprime2(14, 15) 
1000000 loops, best of 3: 486 ns per loop

對於Python <= 3.4，您可以使用fractions.gcd，但如@ user2357112的評論中所述，它未在中實現。其實，真的沒有動力去實際使用它，its implementation is exactly the same as yours.

來源

2016-09-24 17:32:28

然而，在3.5之前的版本中並沒有太多好處，因爲'fractions.gcd'是用Python而不是C編寫的。 – user2357112

高效檢查兩個數字是否是共素數（相對素數）？

回答

相關問題