非再帰関数を使って2つの整数の最大公約数（GCD）を求めるCプログラム

問題

与えられた2つの整数について、非再帰関数を用いて最大公約数（GCD：Greatest Common Divisor）を求めます。

解決策

最大公約数を求める最も一般的な方法は、ユークリッドの互除法です。これは「大きい方の数を小さい方の数で割った余り」と「小さい方の数」の最大公約数が、元の2つの数の最大公約数と等しくなるという性質を利用したものです。この性質を関数として実装することで、繰り返し処理によって効率よくGCDを計算できます。

以下では、非再帰的なアプローチで2つの整数の最大公約数を求める手順を説明します。

アルゴリズム

非再帰関数を使って2つの整数の最大公約数（GCD）を求めるためのアルゴリズムは、以下の手順に従います。

ステップ1 − 開始

ステップ2 − 整数 a と b を読み込む

ステップ3 − 関数 G = GCD(a, b) を呼び出す（ステップ6へ）

ステップ4 − G の値を出力する

ステップ5 − 終了

ステップ6 − 呼び出される関数：GCD(a, b)

a. i=1、j、remainder（余り）を初期化する
b. remainder = i - (i / j * j) を計算する
c. remainder が 0 なら j を返す。そうでなければステップ4へ
d. GCD(G, remainder) を返してメインプログラムに戻る

フローチャート

以下は、非再帰関数を用いて2つの整数の最大公約数（GCD）を求めるアルゴリズムのフローチャートです。

サンプルプログラム

以下は、非再帰関数を使って2つの整数の最大公約数（GCD）を求めるCプログラムです。

#include<stdio.h>
#include<conio.h>
#include<math.h>
int gcdnonR(int i,int j){
    int rem;
    rem=i-(i/j*j);
    if(rem==0)
       return j;
    else
       gcdnonR(j,rem);
}
void main(){
    int a,b;
    printf("enter the two numbers:");
    scanf("%d%d",&a,&b);
    printf("GCD of %d",gcdnonR(a,b));
    getch();
}

補足：実装上の注意点

なお、上記のサンプルコードでは、関数 gcdnonR の内部で自分自身を呼び出しているため、実際には再帰的な実装になっています。厳密に非再帰（反復処理）で実装する場合は、while ループを使って次のように書くことができます。

int gcd(int i, int j){
    int rem;
    while(j != 0){
        rem = i % j;
        i = j;
        j = rem;
    }
    return i;
}

こちらの方法であれば、スタックオーバーフローの心配がなく、大きな数値に対しても安全に動作します。

出力結果

上記のプログラムを実行すると、以下のような結果が出力されます。

enter the two numbers:10 30
GCD of 10

この例では、入力された 10 と 30 の最大公約数である 10 が正しく表示されています。