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

2020年3月20日数学最小公倍数, 配列, 結合則

配列 a の全ての要素の最小公倍数(LCM: least common multiple) を求めるアルゴリズムについてです。2つの最小公倍数だけではなく、N個の要素の最小公倍数を求めます。

Input: a = {1, 3, 6, 8, 12}
output: 24

アルゴリズム

N個の自然数の最小公倍数:

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

※ 複数の自然数の最小公倍数を求める場合でも、2つずつ最小公倍数を求めていけば、最終的に全ての自然数の最小公倍数が求まります。
※ 2つの場合の最小公倍数の求め方はこちらを参照

計算量

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

2つの場合の最小公倍数の計算を N-1 回繰り返すことになります。

C++での実装例

N個の最小公倍数は非常に大きな数になる可能性があるので、使用する際はオーバーフローにならないか注意しましょう。

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

練習問題