Javaで数値配列の最小公倍数（LCM）を求める方法

L.C.M.（最小公倍数、Least Common Multiple）とは、2つ以上の値のどちらの倍数にもなる最小の正の整数のことです。

例として、3と4の倍数を並べてみましょう。

3 → 3, 6, 9, 12, 15 ...

4 → 4, 8, 12, 16, 20 ...

両方に共通する最小の倍数は12なので、3と4の最小公倍数は12になります。

最小公倍数の求め方のポイント

配列内のすべての数値の最小公倍数を求める場合は、2つの数の最小公倍数を順番に計算して畳み込んでいく方法が効率的です。最小公倍数は、最大公約数（GCD）を使って次の式で求められます。

LCM(a, b) = a × b ÷ GCD(a, b)

最大公約数は「ユークリッドの互除法」と呼ばれる古典的なアルゴリズムを使うと、非常に効率よく計算できます。

プログラム

以下の例では、整数配列の最小公倍数を計算しています。

public class LCMofArrayOfNumbers {
    // 最大公約数（GCD）をユークリッドの互除法で求める
    static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }

    // 2つの数の最小公倍数（LCM）を求める
    static int lcm(int a, int b) {
        return a / gcd(a, b) * b;
    }

    public static void main(String args[]) {
        int[] myArray = {25, 50, 125, 625};
        int lcm = myArray[0];

        // 配列の先頭から順に、これまでのLCMと次の要素のLCMを計算
        for (int i = 1; i < myArray.length; i++) {
            lcm = lcm(lcm, myArray[i]);
        }

        System.out.println("配列の数値の最小公倍数 : " + lcm);
    }
}

実行結果

配列の数値の最小公倍数 : 1250

プログラムの解説

1. ユークリッドの互除法によるGCD計算

gcdメソッドは、2つの数の最大公約数をユークリッドの互除法で求めます。剰余計算を繰り返し、余りが0になった時点の値が最大公約数となります。計算量は非常に少なく、大きな数でも高速に処理できます。

2. GCDを利用したLCM計算

lcmメソッドでは「a ÷ GCD(a, b) × b」という順序で計算しています。先に割り算を行うことで、掛け算の中間値が大きくなりすぎてint型の範囲を超える（オーバーフローする）のを防いでいます。

3. 配列全体への展開

配列の最初の要素を初期値とし、2番目以降の要素と順にLCMを計算していくことで、配列全体の最小公倍数が求められます。この例では、LCM(25, 50) = 50、LCM(50, 125) = 250、LCM(250, 625) = 1250 と計算が進み、最終的な結果は1250になります。

この手法を使えば、3つ以上の任意の個数の数値に対しても、同じロジックで最小公倍数を正確に求めることができます。