Python 有效地检查两个数字是否互质（相对质数）？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/39678984/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Efficiently check if two numbers are co-primes (relatively primes)?
提问by Erba Aitbayev
What is the most efficient ("pythonic") way to test/check if two numbers are co-primes (relatively prime) in Python.
在 Python 中测试/检查两个数字是否互质（相对质数）的最有效（“pythonic”）方法是什么。
For the moment I have this code:
目前我有这个代码：
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
Can the code for checking/testing if two numbers are relatively prime be considered "Pythonic" or there is some better way?
检查/测试两个数字是否互质的代码可以被认为是“Pythonic”还是有更好的方法？
回答by Dimitris Fasarakis Hilliard
The only suggestion for improvement might be with your function gcd. Namely, you could use gcdthat's defined in math(for Python 3.5) for a speed boost.
唯一的改进建议可能是您的功能gcd。也就是说，您可以使用（对于 Python ）中gcd定义的math来3.5提高速度。
Defining coprime2that uses the built-in version of gcd:
定义coprime2使用 的内置版本gcd：
from math import gcd as bltin_gcd
def coprime2(a, b):
return bltin_gcd(a, b) == 1
You almost cut down execution speed by half due to the fact that math.gcdis implemented in C(see math_gcdin mathmodule.c):
你几乎减少执行速度的一半归因于这样的事实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
For Python <= 3.4you could use fractions.gcdbut, as noted in a comment by @user2357112, it is not implemented in C. Actually, there's really no incentive to actually use it, its implementation is exactly the same as yours.
对于 Python，<= 3.4您可以使用，fractions.gcd但正如@user2357112 在评论中指出的那样，它没有在C. 实际上，真的没有动力去实际使用它，它的实现和你的完全一样。
