有效地检查两个数字是否为互质数（相对质数）？ [英] Efficiently check if two numbers are co-primes (relatively primes)?

问题描述

测试/检查两个数字是否互为素数（相对素数）的最有效（ pythonic）方法是什么。

What is the most efficient ("pythonic") way to test/check if two numbers are co-primes (relatively prime) in 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还是有更好的方法？

Can the code for checking/testing if two numbers are relatively prime be considered "Pythonic" or there is some better way?

推荐答案

唯一的改进建议可能是使用函数 gcd 。即，您可以使用 gcd 数学（对于Python 3.5 ）中定义的c> 以提高速度。

The only suggestion for improvement might be with your function gcd. Namely, you could use gcd that's defined in math (for Python 3.5) for a speed boost.

使用内置版本 gcd 定义 coprime2 ：

from math import gcd as bltin_gcd

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

由于以下事实，您几乎将执行速度降低了一半在 C 中实现了 math.gcd （请参见 mathmodule.c math_gcd c> ）：

You almost cut down execution speed by half due to the fact that math.gcd is implemented in 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的注释中所述，它未在 C 中实现。实际上，实际上没有任何动机去使用它，其实现与您的实现完全相同。

For Python <= 3.4 you could use fractions.gcd but, 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.

这篇关于有效地检查两个数字是否为互质数（相对质数）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！