高效地检查两个数字是否互质（没有共同因数）？

Question

在Python中，检测/检查两个数字是否互质（互素）最高效的方法是什么（“pythonic”）。

目前我有这段代码：

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

检查/测试两个数字是否互质的代码是否可以被认为是“Pythonic”，还是有更好的方法？

- Erba Aitbayev

---

看起来相当不错。 - khelwood

你当然可以使用 math.gcd，它是一个内置的库，应该更加高效。 - Dimitris Fasarakis Hilliard

注意：math.gcd 是 Python 3.5 中新增的函数，之前是 fractions.gcd。 - mkiever

如果这是你认为需要改进的 可运行代码，请参考[codereview.se]。 - jonrsharpe

Answer 1

唯一的改进建议可能是关于你的函数gcd。也就是说，你可以使用在math中定义的gcd（对于Python 3.5）来提高速度。

定义使用内置版本的gcd的coprime2：

from math import gcd as bltin_gcd

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

由于math.gcd是使用C实现的（请参见mathmodule.c中的math_gcd），因此您几乎将执行速度减半：

%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在评论中指出的那样，它没有在C中实现。实际上，实际上没有动力去使用它，它的实现与您的完全相同。

- Dimitris Fasarakis Hilliard

---

但是在Python 3.5版本之前，由于fractions.gcd是用Python编写而不是C编写，因此受益不如后者明显。 - user2357112

这是一个老问题，但是Python中的数学模块函数通常对于大数字不太好用。它可能会崩溃。我建议使用SymPy或PARI/GP等工具。 - İbrahim İpek

如果您能比较一下这两个函数就太好了：numpy.gcd() 和 math.gdc()。 - Rajesh Swarnkar