C++でn個の数のGCD（最大公約数）とLCM（最小公倍数）を求めるプログラム

本記事では、複数の整数からGCD（最大公約数）とLCM（最小公倍数）を求めるC++プログラムを解説します。

GCD（Greatest Common Divisor：最大公約数）とは、2つ以上の整数（すべてがゼロではないもの）に共通する約数の中で最大となる正の整数のことです。英語では Greatest Common Factor（最大公因子）とも呼ばれます。

一方、LCM（Least Common Multiple：最小公倍数）とは、2つの数のどちらの倍数にもなる数のうち、ゼロ以外で最小の数を指します。

アルゴリズム

まず、処理の流れを擬似コードで確認しましょう。GCDの計算には、剰余を繰り返し求める「ユークリッドの互除法」が使われています。

開始
　　2つの数を入力として受け取る
　　関数 gcd() を呼び出して GCD を求める
　　関数 lcm() を呼び出して LCM を求める

　　gcd(number1, number2)
　　　r, a, b を宣言する
　　　r = 0 を代入
　　　a = (number1 > number2) ? number1 : number2
　　　b = (number1 < number2) ? number1 : number2
　　　r = b
　　　(a % b != 0) の間繰り返す:
　　　　　r = a % b
　　　　　a = b
　　　　　b = r
　　　r を返す

　　lcm(number1, number2)
　　　a を宣言する
　　　a = (number1 > number2) ? number1 : number2
　　　無限ループ:
　　　　　もし (a % number1 == 0 かつ a % number2 == 0) ならば
　　　　　　　a を返す
　　　　　a をインクリメント
終了

GCDの仕組み（ユークリッドの互除法）

大きい方の数を小さい方の数で割った余りを求め、次に「割る数」と「余り」のペアで同じ操作を繰り返します。余りが0になったときの割る数が最大公約数となります。

LCMの仕組み

大きい方の数から順に1ずつ増やしながら、両方の数で割り切れるかどうかを判定します。最初に両方で割り切れた値が最小公倍数です。

サンプルコード

#include<iostream>
using namespace std;
int gcd(int m, int n) {
    int r = 0, a, b;
    a = (m > n) ? m : n;
    b = (m < n) ? m : n;
    r = b;
    while (a % b != 0) {
        r = a % b;
        a = b;
        b = r;
    }
    return r;
}
int lcm(int m, int n) {
    int a;
    a = (m > n) ? m : n;
    while (true) {
        if (a % m == 0 && a % n == 0)
            return a;
        ++a;
    }
}
int main(int argc, char **argv) {
    cout << "Enter the two numbers: ";
    int m, n;
    cin >> m >> n;
    cout << "The GCD of two numbers is: " << gcd(m, n) << endl;
    cout << "The LCM of two numbers is: " << lcm(m, n) << endl;
    return 0;
}

実行結果

Enter the two numbers:
7
6
The GCD of two numbers is: 1
The LCM of two numbers is: 42

n個の数へ拡張するには

上記のコードは2つの数を扱いますが、次の性質を利用すれば3つ以上の数にも対応できます。

• GCDの場合：gcd(a, b, c) = gcd(gcd(a, b), c)
• LCMの場合：lcm(a, b, c) = lcm(lcm(a, b), c)

つまり、配列の先頭から順に2つずつgcd()やlcm()を適用していけば、任意の個数の整数についても最大公約数・最小公倍数を求められます。