[C言語] 最小公倍数を求める方法

2023-09-122024-08-25

最小公倍数（LCM）は、2つ以上の整数の中で最小の共通の倍数を指します。C言語で最小公倍数を求めるには、通常、最大公約数（GCD）を利用します。

具体的には、2つの整数 a と b の最小公倍数は、(a * b) / GCD(a, b) で計算できます。

この方法は、GCDを求めるためにユークリッドの互除法を使用することが一般的です。ユークリッドの互除法は、2つの整数の最大公約数を効率的に計算するアルゴリズムです。

この記事でわかること

反復法と再帰法による最小公倍数の計算方法
複数の整数の最小公倍数を求める方法
配列を用いた最小公倍数の計算手法
大きな数を扱う際の注意点と対策

目次から探す

最小公倍数を求めるプログラムの作成

最小公倍数(LCM: Least Common Multiple)は、2つ以上の整数の中で最小の共通の倍数を指します。

C言語で最小公倍数を求める方法として、反復法と再帰法があります。

それぞれの方法を詳しく見ていきましょう。

反復法による最小公倍数の計算

反復法では、2つの整数の最大公約数(GCD: Greatest Common Divisor)を利用して最小公倍数を求めます。

以下にその手順を示します。

#include <stdio.h>
// 最大公約数を求める関数
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}
// 最小公倍数を求める関数
int lcm(int a, int b) {
    return (a * b) / gcd(a, b);
}
int main() {
    int num1 = 12, num2 = 18;
    printf("最小公倍数: %d\n", lcm(num1, num2));
    return 0;
}

最小公倍数: 36

このプログラムでは、まず最大公約数を求め、その結果を用いて最小公倍数を計算しています。

反復法は、計算がシンプルで理解しやすいのが特徴です。

再帰法による最小公倍数の計算

再帰法では、再帰的に最大公約数を求め、その結果を用いて最小公倍数を計算します。

以下にその手順を示します。

#include <stdio.h>
// 再帰的に最大公約数を求める関数
int gcd_recursive(int a, int b) {
    if (b == 0)
        return a;
    return gcd_recursive(b, a % b);
}
// 最小公倍数を求める関数
int lcm_recursive(int a, int b) {
    return (a * b) / gcd_recursive(a, b);
}
int main() {
    int num1 = 12, num2 = 18;
    printf("最小公倍数: %d\n", lcm_recursive(num1, num2));
    return 0;
}

最小公倍数: 36

このプログラムでは、再帰的に最大公約数を求め、その結果を用いて最小公倍数を計算しています。

再帰法は、コードが簡潔である一方、再帰呼び出しのオーバーヘッドがあるため、注意が必要です。

反復法と再帰法のどちらを選ぶかは、プログラムの目的や好みによりますが、どちらも最小公倍数を効率的に求めることができます。

応用例

最小公倍数の計算は、2つの整数に限らず、複数の整数や配列を扱う場合にも応用できます。

また、大きな数を扱う際には特別な注意が必要です。

以下にそれぞれの応用例を示します。

複数の数の最小公倍数を求める

複数の整数の最小公倍数を求めるには、2つずつ最小公倍数を計算し、それを順次他の数と組み合わせていく方法が一般的です。

#include <stdio.h>
// 最大公約数を求める関数
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}
// 最小公倍数を求める関数
int lcm(int a, int b) {
    return (a * b) / gcd(a, b);
}
// 複数の数の最小公倍数を求める関数
int lcm_multiple(int numbers[], int size) {
    int result = numbers[0];
    for (int i = 1; i < size; i++) {
        result = lcm(result, numbers[i]);
    }
    return result;
}
int main() {
    int numbers[] = {12, 18, 24};
    int size = sizeof(numbers) / sizeof(numbers[0]);
    printf("複数の数の最小公倍数: %d\n", lcm_multiple(numbers, size));
    return 0;
}