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

  • Z时代
  • 2024-01-10
  • 分类：问答

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

回答：

改善的唯一建议可能是您的功能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。实际上，

实际上没有任何动机去使用它，

它的实现与您的实现完全相同。

以上是 有效检查两个数字是否为互质数（相对质数）？ 的全部内容， 来源链接： utcz.com/qa/431431.html

回到顶部