数値処理

[C言語] 最大公約数をfor文を使って求める方法を解説

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

C言語で最大公約数を求める方法の一つに、for文を使った方法があります。

この方法では、2つの整数のうち小さい方の数から1まで順にループを回し、両方の数を割り切れる最大の数を見つけます。

具体的には、for文を用いて、割り切れるかどうかを%演算子で確認し、条件を満たす最初の数を最大公約数とします。

この方法はシンプルで理解しやすいですが、効率的にはユークリッドの互除法に劣ります。

目次から探す

for文を使った最大公約数の求め方
応用例
まとめ

for文を使った最大公約数の求め方

for文の基本構造

C言語におけるfor文は、特定の条件が満たされるまで繰り返し処理を行うための制御構造です。

基本的な構造は以下の通りです。

for (初期化; 条件; 更新) {
    // 繰り返し実行する処理
}

初期化: ループの開始時に一度だけ実行される部分です。

通常、ループカウンタの初期化に使用されます。

条件: 各ループの反復の開始時に評価される式です。

この条件が真である限り、ループは続行されます。

更新: 各反復の終わりに実行される部分で、通常はループカウンタの更新に使用されます。

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

最大公約数(GCD: Greatest Common Divisor)を求めるための基本的なアルゴリズムの一つに、単純な反復法があります。

この方法では、2つの整数のうち小さい方の数から1まで順に割り算を試み、両方の数を割り切れる最大の数を見つけます。

アルゴリズムの流れは以下の通りです。

2つの整数aとbを用意する。
aとbのうち小さい方の数をminとする。
minから1までの数をfor文で順に試す。
aとbの両方を割り切れる数が見つかったら、それが最大公約数。

サンプルコードの解説

以下に、for文を使って最大公約数を求めるC言語のサンプルコードを示します。

#include <stdio.h>
int main() {
    int a, b, gcd, i;
    
    // ユーザーから2つの整数を入力
    printf("2つの整数を入力してください: ");
    scanf("%d %d", &a, &b);
    
    // aとbのうち小さい方をminとする
    int min = (a < b) ? a : b;
    
    // minから1までの数で割り切れるかを確認
    for (i = 1; i <= min; i++) {
        if (a % i == 0 && b % i == 0) {
            gcd = i; // 両方を割り切れる数をgcdに保存
        }
    }
    
    // 最大公約数を出力
    printf("最大公約数は: %d\n", gcd);
    
    return 0;
}

2つの整数を入力してください: 48 18
最大公約数は: 6

このプログラムは、ユーザーから2つの整数を入力させ、それらの最大公約数をfor文を使って計算します。

minから1までの数を順に試し、両方の数を割り切れる最大の数をgcdとして保存します。

最終的に、計算された最大公約数を出力します。

応用例

ユークリッドの互除法との比較

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

この方法は、2つの整数のうち大きい方を小さい方で割り、その余りで再び割り算を繰り返すことで最大公約数を求めます。

for文を使った単純な反復法と比較すると、ユークリッドの互除法は計算回数が少なく、特に大きな数に対して高速に動作します。

比較項目	for文を使った方法	ユークリッドの互除法
アルゴリズムの複雑さ	O(n)	O(log(min(a, b)))
実装の容易さ	簡単	やや複雑
計算速度	遅い(大きな数に対して)	速い

複数の数値の最大公約数を求める

複数の数値の最大公約数を求める場合、2つの数の最大公約数を求める方法を繰り返し適用します。

例えば、3つの数a, b, cの最大公約数を求めるには、まずaとbの最大公約数を求め、それをcと比較して最大公約数を求めます。

#include <stdio.h>
// 2つの数の最大公約数を求める関数
int gcd(int x, int y) {
    int i, gcd;
    int min = (x < y) ? x : y;
    for (i = 1; i <= min; i++) {
        if (x % i == 0 && y % i == 0) {
            gcd = i;
        }
    }
    return gcd;
}
int main() {
    int a, b, c, result;
    
    // ユーザーから3つの整数を入力
    printf("3つの整数を入力してください: ");
    scanf("%d %d %d", &a, &b, &c);
    
    // 3つの数の最大公約数を求める
    result = gcd(gcd(a, b), c);
    
    // 結果を出力
    printf("最大公約数は: %d\n", result);
    
    return 0;
}

最大公約数を用いた分数の約分

最大公約数を用いることで、分数を簡単に約分することができます。

分子と分母の最大公約数を求め、その値で分子と分母を割ることで、分数を最も簡単な形にすることができます。

#include <stdio.h>
// 2つの数の最大公約数を求める関数
int gcd(int x, int y) {
    int i, gcd;
    int min = (x < y) ? x : y;
    for (i = 1; i <= min; i++) {
        if (x % i == 0 && y % i == 0) {
            gcd = i;
        }
    }
    return gcd;
}
int main() {
    int numerator, denominator, divisor;
    
    // ユーザーから分子と分母を入力
    printf("分子と分母を入力してください: ");
    scanf("%d %d", &numerator, &denominator);
    
    // 分子と分母の最大公約数を求める
    divisor = gcd(numerator, denominator);
    
    // 分数を約分
    numerator /= divisor;
    denominator /= divisor;
    
    // 結果を出力
    printf("約分された分数は: %d/%d\n", numerator, denominator);
    
    return 0;
}