与えられた二つの数字が互いに素ているかどうかを確認するための最速の方法は何ですか？

Question

一つの方法は、のGCD自分のを計算し、それが1であるかどうかを確認することです。

いくつかのより高速な方法はありますか？

Answer 1

ユークリッドアルゴリズム（gcdを計算）が非常に高速です。二つの数が[1, n]からランダムに一様に描かれている場合、そのgcdを計算するステップの平均数はO(log n)あります。各ステップに必要な平均の計算時間は、桁数に二次である。

があり（すなわち、各ステップは桁数でsubquadraticある）幾分良好に機能する選択肢があるが、それらは非常に大きな整数でのみ有効です。 Schönhageのアルゴリズムとsubquadratic整数GCD計算するで、例えば、参照してください。

Answer 2

あなたは除算/剰余がシフトよりもかなり高価であるためにマシン上で実行している場合、バイナリ考えますGCD でます。