数値処理

[C言語] 3つの数値から最小公倍数を求める方法

2025-01-18更新日: 2025-01-18

C言語で3つの数値から最小公倍数（LCM）を求めるには、まず2つの数値の最小公倍数を求め、その結果を3つ目の数値と組み合わせて再度最小公倍数を計算します。

最小公倍数は最大公約数（GCD）を利用して計算できます。具体的には、2つの数値aとbの最小公倍数は、(a * b) / GCD(a, b)で求められます。

この方法を3つの数値に適用することで、効率的に最小公倍数を求めることが可能です。

目次から探す

3つの数値から最小公倍数を求めるアルゴリズム
応用例
まとめ

3つの数値から最小公倍数を求めるアルゴリズム

3つの数値から最小公倍数(LCM)を求めるには、まず最大公約数(GCD)を理解することが重要です。

GCDを求めるための効率的な方法として、ユークリッドの互除法があります。

この方法を用いて、2つの数値のLCMを求め、その結果を用いて3つの数値のLCMを計算します。

ユークリッドの互除法を用いた最大公約数の求め方

ユークリッドの互除法は、2つの整数の最大公約数を求めるための効率的なアルゴリズムです。

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

2つの整数 a と b を用意します。
b が0でない限り、a を b で割った余りを r とします。
a に b を、b に r を代入します。
b が0になったとき、a が最大公約数です。

以下は、C言語での実装例です。

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

最大公約数: 6

このプログラムは、48と18の最大公約数を求めるもので、結果は6です。

2つの数値から最小公倍数を求める

2つの数値 a と b の最小公倍数は、次の式で求められます。

[ \text{LCM}(a, b) = \frac{|a \times b|}{\text{GCD}(a, b)} ]

この式を用いて、C言語での実装を示します。

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

最小公倍数: 144

このプログラムは、48と18の最小公倍数を求めるもので、結果は144です。

3つの数値の最小公倍数を求める

3つの数値 a, b, c の最小公倍数は、2つの数値の最小公倍数を繰り返し計算することで求められます。

具体的には、次のように計算します。

a と b の最小公倍数を求めます。
その結果と c の最小公倍数を求めます。

以下にC言語での実装例を示します。

#include <stdio.h>
// 最大公約数を求める関数
int gcd(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}
// 最小公倍数を求める関数
int lcm(int a, int b) {
    return (a * b) / gcd(a, b);
}
int main() {
    int a = 48, b = 18, c = 30;
    int lcm_ab = lcm(a, b);
    int lcm_abc = lcm(lcm_ab, c);
    printf("3つの数値の最小公倍数: %d\n", lcm_abc);
    return 0;
}

3つの数値の最小公倍数: 720

このプログラムは、48, 18, 30の3つの数値の最小公倍数を求めるもので、結果は720です。

応用例

最小公倍数の計算は、さまざまな場面で応用可能です。

ここでは、配列を用いた複数の数値の最小公倍数の計算、ユーザー入力による動的な数値の処理、そして最小公倍数を用いた問題解決の例を紹介します。

配列を用いた複数の数値の最小公倍数の計算

複数の数値の最小公倍数を求める場合、配列を用いると便利です。

以下に、配列内の数値すべての最小公倍数を求めるC言語の例を示します。

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

配列内の数値の最小公倍数: 720

このプログラムは、配列内の数値すべての最小公倍数を求めるもので、結果は720です。

ユーザー入力による動的な数値の処理

ユーザーからの入力を受け取り、その数値の最小公倍数を計算するプログラムを作成することも可能です。

以下にその例を示します。

#include <stdio.h>
// 最大公約数を求める関数
int gcd(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}
// 最小公倍数を求める関数
int lcm(int a, int b) {
    return (a * b) / gcd(a, b);
}
// 配列内の数値の最小公倍数を求める関数
int lcm_array(int arr[], int n) {
    int result = arr[0];
    for (int i = 1; i < n; i++) {
        result = lcm(result, arr[i]);
    }
    return result;
}
int main() {
    int n;
    printf("数値の個数を入力してください: ");
    scanf("%d", &n);
    
    int numbers[n];
    printf("数値を入力してください: ");
    for (int i = 0; i < n; i++) {
        scanf("%d", &numbers[i]);
    }
    
    printf("入力された数値の最小公倍数: %d\n", lcm_array(numbers, n));
    return 0;
}

数値の個数を入力してください: 3
数値を入力してください: 48 18 30
入力された数値の最小公倍数: 720

このプログラムは、ユーザーが入力した数値の最小公倍数を求めるもので、動的に数値を処理します。

最小公倍数を用いた問題解決の例

最小公倍数は、スケジュールの調整や周期的なイベントの管理など、さまざまな問題解決に役立ちます。

例えば、異なる周期で発生するイベントが同時に発生する最小の時間を求めることができます。

例として、3つのイベントがそれぞれ4日、6日、8日ごとに発生する場合、これらが同時に発生する最小の日数を求めることができます。

#include <stdio.h>
// 最大公約数を求める関数
int gcd(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}
// 最小公倍数を求める関数
int lcm(int a, int b) {
    return (a * b) / gcd(a, b);
}
int main() {
    int event1 = 4, event2 = 6, event3 = 8;
    int lcm_12 = lcm(event1, event2);
    int lcm_123 = lcm(lcm_12, event3);
    printf("3つのイベントが同時に発生する最小の日数: %d\n", lcm_123);
    return 0;
}

3つのイベントが同時に発生する最小の日数: 24

このプログラムは、3つのイベントが同時に発生する最小の日数を求めるもので、結果は24日です。

まとめ

最小公倍数の計算は、C言語を用いて効率的に行うことができます。

この記事では、ユークリッドの互除法を用いた最大公約数の求め方から、配列を用いた応用例までを解説しました。

最小公倍数の計算は、スケジュール調整や周期的なイベントの管理など、実生活の問題解決にも役立ちます。

この記事を参考に、ぜひ自分のプログラムに最小公倍数の計算を取り入れてみてください。