C++でGCDを使わずに3つ以上の数（配列）の最小公倍数（LCM）を求める方法

配列Aが与えられたとき、GCD（最大公約数）の演算を使わずに、すべての要素のLCM（最小公倍数）を求める方法を解説します。例えば、配列が {4, 6, 12, 24, 30} の場合、LCMは120になります。

2つの数値のLCMは簡単に計算できます。以下のアルゴリズムに従うことでLCMを求められます。

getLCM(a, b) のアルゴリズム

begin
    if a > b, then m := a, otherwise m := b
       while true do
          if m is divisible by both a and b, then return m
            m := m + 1
   done
end

このアルゴリズムの考え方はシンプルです。まずaとbのうち大きい方をmとし、mがaとbの両方で割り切れるまで1ずつ増やしていきます。割り切れた時点でのmが最小公倍数となります。

この関数を使って、まず配列の最初の2つの要素のLCMを求めます。次に、その結果と3番目の要素のLCMを計算し、さらにその結果と4番目の要素のLCMを計算する……というように順番に処理を進めていくことで、配列全体のLCMを求めることができます。

C++による実装例

#include <iostream>
using namespace std;
int getLCM(int a, int b){
    int m;
    m = (a > b) ? a : b;
    while(true){
        if(m % a == 0 && m % b == 0)
        return m;
        m++;
    }
}
int getLCMArray(int arr[], int n){
    int lcm = getLCM(arr[0], arr[1]);
    for(int i = 2; i < n; i++){
        lcm = getLCM(lcm, arr[i]);
    }
    return lcm;
}
int main() {
    int arr[] = {4, 6, 12, 24, 30};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "LCM of array elements: " << getLCMArray(arr, n);
}

実行結果

LCM of array elements: 120

コードの解説

getLCM関数：引数として受け取った2つの整数a、bのうち大きい方を初期値mとし、mがaとbの両方で割り切れるまでインクリメントを繰り返します。条件を満たした時点でmを返します。

getLCMArray関数：まず配列の先頭2要素のLCMを計算し、その後はforループで3番目以降の要素と順にLCMを求めていきます。これにより、GCDを使わずに配列全体の最小公倍数を導き出せます。

なお、この方法は直感的で理解しやすい反面、数値が大きくなるとループ回数が増えて計算時間が長くなる点に注意が必要です。競技プログラミングなどでは、通常「a × b ÷ GCD(a, b)」という式で効率的にLCMを求めることが一般的ですが、本記事のようにGCDを使わないアプローチもアルゴリズムの学習として有用です。