配列の全ての要素(N個)の最大公約数(GCD)を求めるアルゴリズム

2020年3月21日数学最大公約数, 配列, 結合則

配列 A が与えられて、その全ての要素の最大公約数(GCD)を求めることを考えます。2つの最大公約数だけではなく、N個の要素の最大公約数を求めます。

例:

Input: A = {36, 12, 48}
Output: 12

アルゴリズム

N個の自然数の最大公約数:

  1. リスト {\(a_1, a_2, a_3,…, a_N\)} の要素数が 1 つになるまで以下を繰り返す
    • リストから2つ選んで最大公約数 gcd を計算し、リストに加える
  2. 残った 1 つが全体の最大公約数

※ 複数の自然数の最大公約数を求める場合でも、2つずつ最大公約数を求めていけば、最終的に全ての自然数の最大公約数が求まります。

※ 2つの場合の最大公約数の求め方はこちらを参照

計算量

  • \(O(N \log( a’ ) )\) (\(a’\) は二番目に大きい数)

2つの最大公約数の計算を N-1 回繰り返すことになります。

C++での実装例

 ※ gcd はC++17 から標準ライブラリに追加されています。以下は C++14 での例です。

練習問題