2つの数値の最小公倍数（LCM）を求めるアルゴリズム

数学において、最小公倍数（LCM：Least Common Multiple）とは、2つの数値のどちらによっても割り切れる最小の正の整数のことです。

LCMは素因数分解など、さまざまな方法で計算できます。この記事で紹介するアルゴリズムでは、大きい方の数値に 1、2、3…n と順に掛けていき、もう一方の数値で割り切れる数が見つかった時点で、それをLCMとして返すというシンプルなアプローチを採用しています。

入力と出力

入力：
2つの数値：6 と 9
出力：
LCMは：18

アルゴリズム

手続きは LCMofTwo(a, b) として定義します。

入力： 2つの数値 a と b（a > b と仮定します）。

出力： a と b の最小公倍数。

Begin
    lcm := a
    i := 2
    while lcm mod b ≠ 0, do
        lcm := a * i
        i := i + 1
    done

    return lcm
End

処理の流れ

1. まず lcm を大きい方の数 a で初期化します。
2. lcm が b で割り切れない間、a に 2、3、4… を掛けた値を lcm に代入していきます。
3. lcm が b で割り切れた時点でループを抜け、その値を結果として返します。

C++による実装例

#include<iostream>
using namespace std;

int findLCM(int a, int b) {     // a の方が b より大きいと仮定
    int lcm = a, i = 2;

    while(lcm % b != 0) {       // b の倍数となる数を探索
        lcm = a*i;
        i++;
    }
    return lcm;                 // a と b の LCM
}

int lcmOfTwo(int a, int b) {
    int lcm;
    if(a>b)                     // 第1引数が大きくなるように入れ替え
        lcm = findLCM(a,b);
    else
        lcm = findLCM(b,a);
    return lcm;
}

int main() {
    int a, b;
    cout << "Enter Two numbers to find LCM: "; cin >> a >> b;
    cout << "The LCM is: " << lcmOfTwo(a,b);
}

このコードでは、findLCM 関数が実際の計算を行い、lcmOfTwo 関数が2つの引数の大小を比較して、大きい方を第1引数として渡す役割を担っています。

実行結果

Enter Two numbers to find LCM: 6 9
The LCM is: 18

6 と 9 の場合、6 × 1 = 6、6 × 2 = 12 はどちらも 9 で割り切れませんが、6 × 3 = 18 は 9 で割り切れるため、LCMは 18 となります。