2つの数がコニール（比較的素数）であるかどうかを効率的にチェックしますか？

Question

（比較的素数）がの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的」二つの数が互いに素である場合を考えることができるか、いくつか良い方法はありますか？

Answer 1

改善のための唯一の提案は、あなたの関数gcdであるかもしれません。つまり、math（Python 3.5）で定義されているgcdをスピードブーストに使用できます。

ビルトインgcdのバージョンを使用していますcoprime2の定義：

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.