python - 有效地检查两个数是否互质(相对质数)？

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”或者是否有更好的方法？

Answer 1

唯一的改进建议可能是您的函数 gcd .即，您可以使用 gcd 在 math 中定义(对于 Python 3.5 )以提高速度。

定义 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 在评论中指出的那样，它没有在 C 中实现。 .实际上，确实没有实际使用它的动机，its implementation is exactly the same as yours.