　　C言語例文集

　ユークリッドの互除法で最大公約数を求める

　2つの自然数をコマンドから入力して、その最大公約数を求めます。最大公約数、GCD(Greatest Common Divisor)とは2つの自然数の共通の約数の中で最大の数のことをいいます。例えば、28(4×7)と12(4×3)の最大公約数は4です。

　プログラムで最大公約数を求める有名なアルゴリズムは、ユーグリッドの互除法です。ユーグリッドの互除法について簡単に説明すると以下のようになります。

　① 2つの自然数x , y(x≧y)において、「xをyで割った余り」＝0ならば、 xとyの最大公約数はyといえる。
　②「xをyで割った余り」＝r (r≠0)ならば、xとyの最大公約数はyとrの最大公約数に等しいといえる。

　①はすぐ理解できると思いますが、②は少し複雑ですので、②について簡単に説明します。
　例えば、2つの自然数xとyの最大公約数をGとおくと、x=x'G、y=y'Ｇ　(x'とy'は互いに素、つまりx'とy'の最大公約数は1)　とすることができます。
　次に、xをyで割ったときの商をq、剰余をrとすると、x=qy+r (0≦r<y)と表せます。この式をrについて解くとr=x-qy となります。
　ここで、2つの自然数xとyは、x=x'Ｇ，y=y'Ｇとおいているので、 r=x'Ｇ-qy'Ｇ=(x'-qy')Ｇと表すことができ、rはGの倍数となります。
　よって、y=y'Ｇ、r=(x'-qy')Ｇであるため、xとyの最大公約数Gは、yとrの最大公約数もGとなります（y'とx'-qy'が互いに素であることの証明は省略）。
　つまり、x、yを最大公約数が同じである小さい数にどんどん置き換えて（x≧rなので）いき、最大公約数を求めています。

　この①と②の性質を利用して、最大公約数を求めます。
　例えば、x = 20、y = 12の最大公約数をユーグリッドの互除法で求めてみます。 20を12で割ると余りはr = 8となります。よって、②より 20と12の最大公約数は12と8の最大公約数と等しいといえます。次に、x = 12、y = 8の最大公約数を求めます。 12を8で割ると余りはr = 4となります。同様に今度はx = 8、y = 4の最大公約数を求めます。 8を4で割ると余りは0であるので、①より8と4の最大公約数は4です。 8と4の最大公約数と12と8の最大公約数と20と12の最大公約数は等しいので、 20と12の最大公約数は4ということになります。

＜サンプルプログラム＞

/****************************************************************************/
#include<stdio.h>

int gcd(int x, int y);  // 最大公約数を求める関数

int main()
{
    int x, y;
    int gcd_num;
    printf("最大公約数を求めます。\n");
    printf("自然数を2つ入力してください。\n");
    printf("1つ目の自然数を入力 -> ");
    scanf("%d", &x);
    printf("2つ目の自然数を入力 -> ");
    scanf("%d", &y);

    gcd_num = gcd(x, y);

    printf("%dと%dの最大公約数は%dです。\n", x, y, gcd_num);
    printf("\n");

    return 0;
}

// 最大公約数を求める関数
int gcd(int x, int y)
{
    int r;

    if(x == 0 || y == 0)  // 引数チェック
    {
        fprintf(stderr, "引数エラーです。\n");
        return 0;
    }

    // ユーグリッドの互除法
    while((r = x % y) != 0)  // yで割り切れるまでループ
    {
        x = y;
        y = r;
    }
    return y;
}
/****************************************************************************/

＜実行結果＞

＜Topページ＞