【C言語】ユークリッドの互除法で最大公約数(GCD)と最小公倍数(LCM)を求めるプログラム

問題

ユークリッドの互除法を実装し、2つの整数の最大公約数(GCD)と最小公倍数(LCM)を求めて、入力された整数とあわせて結果を出力するプログラムを作成します。

解法の考え方

ユークリッドの互除法は、2つの整数 x と y の最大公約数を求めるための古典的なアルゴリズムです。「x を y で割った余り r を求め、次に y と r の組に対して同じ操作を繰り返す」ことを、余りが 0 になるまで続けると、そのときの割る数が最大公約数となります。

また、最小公倍数は「2つの整数の積 ÷ 最大公約数」という関係式から簡単に求められます。

GCDとLCMを求めるメインの処理は次のようになっています。

if(firstno*secondno!=0){
    gcd=gcd_rec(firstno,secondno);
    printf("\nThe GCD of %d and %d is %d\n",firstno,secondno,gcd);
    printf("\nThe LCM of %d and %d is %d\n",firstno,secondno,(firstno*secondno)/gcd);
}

実際に最大公約数を計算しているのは、再帰呼び出しを行う次の関数です。

int gcd_rec(int x, int y){
    if (y == 0)
       return x;
    return gcd_rec(y, x % y);
}

y が 0 になった時点での x が最大公約数となるため、それを返します。それ以外の場合は、y と「x を y で割った余り」を新しい引数として自分自身を再度呼び出します。

Cプログラム

以下が、ユークリッドの互除法を実装して2つの整数の最大公約数(GCD)と最小公倍数(LCM)を求めるCプログラムです。

#include<stdio.h>
int gcd_rec(int,int);
void main(){
    int firstno,secondno,gcd;
    printf("Enter the two no.s to find GCD and LCM:");
    scanf("%d%d",&firstno,&secondno);
    if(firstno*secondno!=0){
        gcd=gcd_rec(firstno,secondno);
        printf("\nThe GCD of %d and %d is %d\n",firstno,secondno,gcd);
        printf("\nThe LCM of %d and %d is %d\n",firstno,secondno,(firstno*secondno)/gcd);
    }
    else
        printf("One of the entered no. is zero:Quitting\n");
}

/*Function for Euclid's Procedure*/
int gcd_rec(int x, int y){
    if (y == 0)
        return x;
    return gcd_rec(y, x % y);
}

プログラムの流れ

1. 2つの整数をキーボードから入力する
2. どちらか一方でも 0 の場合は、メッセージを表示して終了する
3. 再帰関数 gcd_rec() によって最大公約数(GCD)を計算する
4. 「2数の積 ÷ GCD」から最小公倍数(LCM)を求めて表示する

実行結果

上記のプログラムをコンパイルして実行すると、次のような出力が得られます。

Enter the two no.s to find GCD and LCM:4 8

The GCD of 4 and 8 is 4

The LCM of 4 and 8 is 8

この実行例では、4 と 8 の最大公約数が 4、最小公倍数が 8 であることが確認できます。