【C言語】最大公約数を求めるプログラムの書き方

2023-09-132024-07-22

この記事では、C言語を使って2つ以上の数値の最大公約数(GCD)と最小公倍数(LCM)を求める方法について解説します。

まず、最大公約数を求めるための「ユークリッドの互除法」というアルゴリズムを紹介し、その基本原理と手順を説明します。

最後に、複数の数値の最大公約数や最小公倍数を求める応用例についても解説します。

目次から探す

最大公約数を求めるアルゴリズム

最大公約数(Greatest Common Divisor, GCD)は、2つ以上の整数の中で、最も大きい共通の約数を指します。

最大公約数を求める方法はいくつかありますが、最も一般的で効率的な方法の一つが「ユークリッドの互除法」です。

ユークリッドの互除法

ユークリッドの互除法の基本原理

ユークリッドの互除法は、紀元前300年頃にギリシャの数学者ユークリッドによって考案されたアルゴリズムです。

この方法は、2つの整数の最大公約数を求めるために、以下の性質を利用します：

2つの整数 (a) と (b) の最大公約数は、(a) を (b) で割った余り (r) と (b) の最大公約数に等しい。
余りが0になるまでこの操作を繰り返すと、最終的に最大公約数が得られる。

このアルゴリズムの基本原理は、次のように表現できます：

ここで、(%) は剰余演算子を示します。

ユークリッドの互除法の手順

ユークリッドの互除法の手順は以下の通りです：

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

具体的な例を見てみましょう。

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

(a = 98), (b = 56)
(98 % 56 = 42) なので、次に (a = 56), (b = 42)
(56 % 42 = 14) なので、次に (a = 42), (b = 14)
(42 % 14 = 0) なので、最大公約数は (14)

再帰を用いたユークリッドの互除法

再帰関数の基本

再帰関数とは、関数が自分自身を呼び出すことで問題を解決する手法です。

再帰関数は、基本ケース(終了条件)と再帰ケース(自己呼び出し)で構成されます。

再帰関数を正しく設計するためには、無限ループに陥らないように基本ケースを適切に設定することが重要です。

再帰を用いたユークリッドの互除法の手順

ユークリッドの互除法は再帰的に実装することができます。

再帰を用いたユークリッドの互除法の手順は以下の通りです：

2つの整数 (a) と (b) を引数として受け取る関数を定義します。
基本ケースとして、(b) が0の場合、(a) を返します。

これが最大公約数です。

再帰ケースとして、を呼び出します。

以下に、再帰を用いたユークリッドの互除法のC言語での実装例を示します：

#include <stdio.h>
// 再帰を用いたユークリッドの互除法
int gcd(int a, int b) {
    if (b == 0) {
        return a; // 基本ケース：bが0の場合、aが最大公約数
    } else {
        return gcd(b, a % b); // 再帰ケース：GCD(b, a % b)を呼び出す
    }
}
int main() {
    int a = 56;
    int b = 98;
    printf("最大公約数: %d\n", gcd(a, b)); // 結果を表示
    return 0;
}

このプログラムを実行すると、56と98の最大公約数である14が出力されます。

再帰を用いることで、コードがシンプルで読みやすくなります。

C言語での実装

基本的なプログラム構造

C言語でプログラムを作成する際には、基本的な構造を理解しておくことが重要です。

ここでは、インクルードガードとヘッダーファイル、そしてメイン関数の構造について説明します。

インクルードガードとヘッダーファイル

インクルードガードは、ヘッダーファイルが複数回インクルードされることを防ぐための仕組みです。

以下は、インクルードガードの基本的な例です。

#ifndef HEADER_FILE_NAME_H
#define HEADER_FILE_NAME_H
// ヘッダーファイルの内容
#endif // HEADER_FILE_NAME_H

このようにすることで、同じヘッダーファイルが複数回インクルードされても、一度だけ読み込まれるようになります。

メイン関数の構造

C言語のプログラムは、必ず main 関数から実行が開始されます。

以下は、基本的な main 関数の構造です。

#include <stdio.h>
int main() {
    // プログラムの処理
    return 0;
}

#include <stdio.h> は標準入出力ライブラリをインクルードしており、printf や scanf などの関数を使用するために必要です。

return 0; はプログラムが正常に終了したことを示します。

ユークリッドの互除法を用いた実装

ここでは、ユークリッドの互除法を用いて最大公約数を求めるプログラムを実装します。

非再帰的な方法と再帰的な方法の両方を紹介します。

非再帰的な実装

非再帰的な方法では、ループを用いて最大公約数を求めます。

以下はその実装例です。

#include <stdio.h>
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}
int main() {
    int num1, num2;
    printf("2つの整数を入力してください: ");
    scanf("%d %d", &num1, &num2);
    int result = gcd(num1, num2);
    printf("最大公約数は %d です\n", result);
    return 0;
}

このプログラムでは、gcd 関数が非再帰的に最大公約数を求めています。

while ループを用いて、b が 0 になるまで計算を繰り返します。

再帰的な実装

再帰的な方法では、関数が自分自身を呼び出して最大公約数を求めます。

以下はその実装例です。

#include <stdio.h>
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}
int main() {
    int num1, num2;
    printf("2つの整数を入力してください: ");
    scanf("%d %d", &num1, &num2);
    int result = gcd(num1, num2);
    printf("最大公約数は %d です\n", result);
    return 0;
}

このプログラムでは、gcd 関数が再帰的に最大公約数を求めています。

b が 0 になるまで再帰的に関数を呼び出します。

入力と出力の処理

プログラムの実行には、ユーザーからの入力を受け取り、その結果を表示することが必要です。

ここでは、標準入力からの読み取りと結果の表示について説明します。

標準入力からの読み取り

標準入力からの読み取りには、scanf 関数を使用します。

以下は、2つの整数を読み取る例です。

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

scanf 関数は、ユーザーが入力した値を指定した変数に格納します。

ここでは、%d フォーマット指定子を用いて整数を読み取っています。

結果の表示

結果の表示には、printf 関数を使用します。

以下は、最大公約数を表示する例です。

int result = gcd(num1, num2);
printf("最大公約数は %d です\n", result);

printf 関数は、指定したフォーマットに従って結果を表示します。

ここでは、%d フォーマット指定子を用いて整数を表示しています。

以上で、C言語を用いた最大公約数を求めるプログラムの基本的な実装方法について説明しました。

非再帰的な方法と再帰的な方法の両方を理解し、適切な場面で使い分けることが重要です。

応用例

複数の数値の最大公約数

複数の数値の最大公約数の求め方

複数の数値の最大公約数を求める場合、2つの数値の最大公約数を順次求めていく方法が一般的です。

例えば、3つの数値 a, b, c の最大公約数を求める場合、まず a と b の最大公約数を求め、その結果と c の最大公約数を求めます。

この方法を繰り返すことで、任意の数の数値の最大公約数を求めることができます。

プログラムの拡張

以下に、複数の数値の最大公約数を求めるプログラムの例を示します。

このプログラムでは、配列を用いて複数の数値を扱い、ユークリッドの互除法を用いて最大公約数を求めます。

#include <stdio.h>
// ユークリッドの互除法を用いた最大公約数の計算
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}
// 配列内の複数の数値の最大公約数を求める
int gcd_array(int arr[], int n) {
    int result = arr[0];
    for (int i = 1; i < n; i++) {
        result = gcd(result, arr[i]);
    }
    return result;
}
int main() {
    int arr[] = {48, 64, 80};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("最大公約数: %d\n", gcd_array(arr, n));
    return 0;
}

このプログラムでは、gcd 関数を用いて2つの数値の最大公約数を計算し、gcd_array 関数で配列内の複数の数値の最大公約数を求めています。

最小公倍数の求め方

最小公倍数の定義

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

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

最大公約数を利用した最小公倍数の求め方

最小公倍数は、最大公約数(GCD: Greatest Common Divisor)を利用して求めることができます。

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

この式を用いることで、最大公約数を計算した後に最小公倍数を求めることができます。

プログラムの実装

以下に、最小公倍数を求めるプログラムの例を示します。

このプログラムでは、先ほどの gcd 関数を利用して最小公倍数を計算します。

#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 / gcd(a, b)) * b;
}
int main() {
    int a = 6;
    int b = 8;
    printf("最小公倍数: %d\n", lcm(a, b));
    return 0;
}

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

lcm 関数では、最大公約数を利用して最小公倍数を効率的に計算しています。

以上で、最大公約数と最小公倍数を求めるプログラムの基本的な実装方法について解説しました。

これらのプログラムを応用することで、より複雑な数値計算やアルゴリズムの実装に役立てることができます。