高效检查两个数字是否为共素(相对素数)？

Question

什么是最有效("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

用于检查/测试两个数字是否相对素数的代码可以被认为是"Pythonic"还是有更好的方法？

Answer 1

唯一的改进建议可能是你的功能gcd.也就是说,你可以使用(在Python中)gcd定义的速度提升.math3.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.实际上,实际上没有动力实际使用它,它的实现与你的完全相同.