高效检查两个数字是否是共素数（相对素数）？

什么是最有效的（“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

高效检查两个数字是否是共素数（相对素数）？

回答

相关问题