有效检查两个数字是否为互质数（相对质数）？

小编典典

有效检查两个数字是否为互质数（相对质数）？

algorithm

什么是测试/检查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”，或者有更好的方法？

阅读 1148

2020-07-28

共1个答案

小编典典

改善的唯一建议可能是您的功能gcd。也就是说，您可以使用（对于Python
）中gcd定义的速度提高速度。math``3.5

定义coprime2使用以下内置版本gcd：

from math import gcd as bltin_gcd

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

你几乎减少执行速度的一半归因于这样的事实math.gcd在实现C（见math_gcd中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。实际上，
实际上没有任何动机去使用它，
它的实现与您的实现完全相同。

2020-07-28