C++で最小公倍数（LCM）を求めるプログラム：初心者向けに2つの方法を解説

最小公倍数（LCM: Least Common Multiple）とは、2つの整数に共通する倍数の中で最も小さい数のことです。プログラミングの基礎的なアルゴリズム学習においても頻出のテーマであり、C++を使えば簡単に求めることができます。

最小公倍数とは？具体例で確認

例として、15と9という2つの数を考えてみましょう。それぞれ素因数分解すると次のようになります。

15 = 5 × 3
9  = 3 × 3

この場合、15と9の両方を割り切れる最小の数、つまり最小公倍数は 45 となります。

方法1：大きい方の数から順に増やしていく方法

まず紹介するのは、最も直感的なアプローチです。2つの数のうち大きい方を初期値とし、その値が両方の数で割り切れるまで1ずつ増やしていきます。

サンプルコード

#include <iostream>
using namespace std;
int main() {
    int a=7, b=5, lcm;
    if(a>b)
    lcm = a;
    else
    lcm = b;
    while(1) {
        if( lcm%a==0 && lcm%b==0 ) {
            cout<<"The LCM of "<<a<<" and "<<b<<" is "<<lcm;
            break;
        }
        lcm++;
    }
    return 0;
}

実行結果

The LCM of 7 and 5 is 35

コードの解説

まず、変数 lcm には2つの数のうち大きい方の値を代入します。これは以下のコード部分で行っています。

if(a>b)
lcm = a;
else
lcm = b;

最小公倍数は必ず元の2つの数以上になるため、大きい方から探索を始めるのが効率的です。

続いて、無限ループ（while(1)）の中で、現在の lcm が a と b の両方で割り切れるかどうかを判定します。割り切れればそれが最小公倍数なので結果を出力してループを抜けます。割り切れない場合は lcm を1ずつ増やしながら条件が満たされるまで繰り返します。

while(1) {
    if( lcm%a==0 && lcm%b==0 ) {
        cout<<"The LCM of "<<a<<" and "<<b<<" is "<<lcm;
        break;
    }
    lcm++;
}

この方法はシンプルで分かりやすい反面、2つの数の差が大きい場合はループ回数が増えて非効率になることがあります。そこで次に、数学的な公式を利用したより効率的な方法を紹介します。

方法2：GCD（最大公約数）を使った公式による方法

2つの数の最小公倍数は、最大公約数（GCD: Greatest Common Divisor）を使って求めることもできます。次の関係式が成り立ちます。

a × b = GCD × LCM

つまり、LCM = (a × b) ÷ GCD と計算できるのです。

サンプルコード

#include<iostream>
using namespace std;
int gcd(int a, int b) {
    if (b == 0)
    return a;
    return gcd(b, a % b);
}
int main() {
    int a = 7, b = 5;
    cout<<"LCM of "<< a <<" and "<< b <<" is "<< (a*b)/gcd(a, b);
    return 0;
}

実行結果

LCM of 7 and 5 is 35

コードの解説

このプログラムでは、まず再帰関数 gcd() を使って最大公約数を求めます。この関数は「ユークリッドの互除法」と呼ばれる古典的なアルゴリズムを実装したものです。

int gcd(int a, int b) {
    if (b == 0)
    return a;
    return gcd(b, a % b);
}

引数 b が0になった時点で a が最大公約数となるため、その値を返します。そうでなければ、自分自身を gcd(b, a % b) として再帰的に呼び出し、剰余を計算し続けることで最大公約数を導き出します。

GCDが求まれば、あとは公式に当てはめてLCMを計算し、結果を出力するだけです。

cout<<"LCM of "<< a <<" and "<< b <<" is "<< (a*b)/gcd(a, b);

まとめ

C++で最小公倍数を求める方法は主に2つあります。

1. 繰り返し探索法： 大きい方の数から順に確認していくシンプルな方法。理解しやすいが、数が大きいと処理に時間がかかる。
2. GCDを利用する方法： ユークリッドの互除法で最大公約数を求め、公式からLCMを計算する効率的な方法。

実用的なプログラムでは後者のGCDを利用する方法が推奨されますが、アルゴリズムの学習としては両方のアプローチを理解しておくと良いでしょう。