【C言語】最大公約数（GCD）と最小公倍数（LCM）を求めるプログラムの書き方

まずは、最大公約数（GCD）の基本から確認していきましょう。

最大公約数（GCD・HCF）とは

2つ以上の整数に共通する約数のうち、最も大きいものを「最大公約数」と呼びます。英語では Highest Common Factor（HCF）、Greatest Common Divisor（GCD）、Greatest Common Measure（GCM）などの名称で呼ばれますが、いずれも同じ概念を指します。

例として、「12と16の最大公約数」を求めてみましょう。

12の約数：1, 2, 3, 4, 6, 12
16の約数：1, 2, 4, 8, 16

両方の数に共通する約数は「1, 2, 4」で、その中で最大のものは4です。したがって、12と16の最大公約数（HCF）は4となります。

最小公倍数（LCM）とは

2つの整数 x と y に対する最小公倍数 LCM(x, y) とは、x と y のどちらの数でも割り切ることができる正の整数のうち、最も小さいものを指します。

例えば、次のようになります。

LCM(2, 3) = 6
LCM(6, 10) = 30

GCDとLCMを求めるCプログラム

以下のプログラムでは、ユークリッドの互除法を使って最大公約数（GCD）を求め、その値をもとに最小公倍数（LCM）を計算しています。

ユークリッドの互除法とは、「大きい方の数を小さい方の数で割った余り」と「小さい方の数」を新しい組み合わせとして、余りが0になるまで割り算を繰り返すアルゴリズムです。余りが0になったときの割る数が最大公約数になります。

また、最小公倍数は次の公式から求められます。

LCM(x, y) = (x × y) ÷ GCD(x, y)

サンプルコード

#include <stdio.h>
int main() {
    int num1, num2, x, y, temp, gcd, lcm;
    printf("Enter two integers\n");
    scanf("%d%d", &x, &y);
    num1 = x;
    num2 = y;
    /* ユークリッドの互除法でGCDを求める */
    while (num2 != 0) {
        temp = num2;
        num2 = num1 % num2;
        num1 = temp;
    }
    gcd = num1;
    lcm = (x*y)/gcd;
    printf("GCD of %d and %d = %d\n", x, y, gcd);
    printf("LCM of %d and %d = %d\n", x, y, lcm);
    return 0;
}

実行結果

プログラムをコンパイルして実行すると、入力した2つの整数に対するGCD（最大公約数）とLCM（最小公倍数）が表示されます。

Run 1:
Enter two integers
6 12
GCD of 6 and 12 = 6
LCM of 6 and 12 = 12

Run 2:
Enter two integers
24 36
GCD of 24 and 36 = 12
LCM of 24 and 36 = 72

実行例1では、6と12の最大公約数が6、最小公倍数が12。実行例2では、24と36の最大公約数が12、最小公倍数が72と、それぞれ正しく計算できていることがわかります。