【C言語】最小公倍数をfor文を使って求める方法

2023-09-122024-07-22

C言語でプログラムを作成する際に、2つの整数の最小公倍数(LCM)を求める方法を知っていると便利です。

この記事では、最大公約数(GCD)を使って最小公倍数を求めるアルゴリズムを解説し、それをC言語で実装する方法をステップバイステップで紹介します。

初心者の方でも理解しやすいように、具体的なサンプルコードとその実行結果も含めて説明しますので、ぜひ参考にしてください。

目次から探す

最小公倍数を求めるアルゴリズム

最小公倍数(LCM: Least Common Multiple)は、2つ以上の整数の公倍数のうち、最小のものを指します。

例えば、6と8の最小公倍数は24です。

最小公倍数を求めるためには、まず最大公約数(GCD: Greatest Common Divisor)を計算する必要があります。

ここでは、最大公約数を使った最小公倍数の求め方について解説します。

最大公約数(GCD)を使った最小公倍数の求め方

最大公約数を使って最小公倍数を求める方法は、以下の手順で行います。

2つの整数の最大公約数(GCD)を求める。
2つの整数の積を最大公約数で割る。

この方法を使うと、効率的に最小公倍数を求めることができます。

ユークリッドの互除法によるGCDの計算

最大公約数を求めるための一般的な方法として、ユークリッドの互除法があります。

ユークリッドの互除法は、以下の手順で行います。

2つの整数 (a) と (b) を用意します(ここで (a > b) とします)。
(a) を (b) で割った余りを (r) とします。
(r) が0でない限り、(a) を (b) に、(b) を (r) に置き換えて手順2に戻ります。
(r) が0になったときの (b) が最大公約数です。

具体的な例を挙げて説明します。

例えば、48と18の最大公約数を求める場合：

(a = 48), (b = 18)
(48 / 18 = 2) 余り (12) ((r = 12))
(a = 18), (b = 12)
(18 / 12 = 1) 余り (6) ((r = 6))
(a = 12), (b = 6)
(12 / 6 = 2) 余り (0) ((r = 0))

したがって、48と18の最大公約数は6です。

GCDを使ったLCMの計算式

最大公約数が求まったら、それを使って最小公倍数を計算します。

2つの整数 (a) と (b) の最小公倍数は、以下の式で求められます。

例えば、48と18の最小公倍数を求める場合：

初期値

最大公約数

最小公倍数

このようにして、最大公約数を使って効率的に最小公倍数を求めることができます。

C言語で最小公倍数を求めるプログラムの実装

ここでは、C言語を使って最小公倍数(LCM)を求めるプログラムを実装する方法を解説します。

具体的には、最大公約数(GCD)を求める関数を作成し、それを利用してLCMを計算します。

必要なヘッダファイルのインクルード

まず、C言語のプログラムを書く際に必要なヘッダファイルをインクルードします。

標準入力・出力を扱うためにstdio.hをインクルードします。

#include <stdio.h>

GCDを求める関数の実装

次に、最大公約数(GCD)を求める関数を実装します。

ここではユークリッドの互除法を用います。

ユークリッドの互除法を使ったGCD関数

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

以下にその関数を示します。

// 最大公約数を求める関数
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

この関数は、引数として2つの整数aとbを受け取り、bが0になるまでループを回して最大公約数を求めます。

LCMを求める関数の実装

次に、GCD関数を利用して最小公倍数(LCM)を求める関数を実装します。

GCD関数を利用したLCM関数

最小公倍数は、2つの整数の積をその最大公約数で割ることで求められます。

以下にその関数を示します。

// 最小公倍数を求める関数
int lcm(int a, int b) {
    return (a * b) / gcd(a, b);
}

この関数は、引数として2つの整数aとbを受け取り、それらの積をGCD関数で求めた最大公約数で割ることで最小公倍数を計算します。

メイン関数の実装

最後に、ユーザーからの入力を受け取り、LCM関数を呼び出して結果を表示するメイン関数を実装します。

ユーザーからの入力を受け取る

まず、ユーザーから2つの整数を入力してもらいます。

int main() {
    int num1, num2;
    printf("2つの整数を入力してください: ");
    scanf("%d %d", &num1, &num2);

LCM関数を呼び出して結果を表示する

次に、入力された2つの整数を使ってLCM関数を呼び出し、その結果を表示します。

int result = lcm(num1, num2);
    printf("%dと%dの最小公倍数は%dです。\n", num1, num2, result);
    return 0;
}

以上で、C言語を使って最小公倍数を求めるプログラムが完成しました。

以下に全体のコードを示します。

#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, num2;
    printf("2つの整数を入力してください: ");
    scanf("%d %d", &num1, &num2);
    int result = lcm(num1, num2);
    printf("%dと%dの最小公倍数は%dです。\n", num1, num2, result);
    return 0;
}

このプログラムを実行すると、ユーザーが入力した2つの整数の最小公倍数が表示されます。

例えば、12と18を入力した場合、結果は36となります。