1 つの方法は、 gcdを計算し、それが 1 かどうかを確認することです。
もっと速い方法はありますか？
質問する
12985 次
2 に答える
12
ユークリッド アルゴリズム (計算gcd) は非常に高速です。2 つの数値が から一様に無作為に抽出される[1, n]場合、それらを計算するための平均ステップ数はgcdですO(log n)。各ステップに必要な平均計算時間は、桁数で 2 次です。
いくらか優れたパフォーマンスを発揮する代替手段があります (つまり、各ステップの桁数が準 2 次です) が、それらは非常に大きな整数に対してのみ有効です。たとえば、シェーンハーゲのアルゴリズムと二次整数 gcd の計算についてを参照してください。
于 2009-09-27T11:54:36.270 に答える
7
除算/剰余がシフトよりもかなり高価なマシンで実行している場合は、バイナリ GCDを検討してください。
于 2009-09-27T13:31:48.463 に答える