C言語のきほん「ユークリッドの互除法」

今回は、「ユークリッドの互除法によって最大公約数」を求めるプログラムである。

ユークリッドの互除法は、二つの整数値の最大公約数を再帰的に求めるアルゴリズムである。

なお、本プログラムは、Windows 11 Home（23H2）上で、 Visual Studio Code（1.88.1）を使用して作成し、gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0　でコンパイルしている。

C言語のインストールについてはこちらをご参照ください。↓

C言語をMacにインストールしよう

MacでC言語プログラミングの学びを始めよう。 WindowsパソコンだけじゃなくてMacでもプログラミング環境を整えてみる。使用したMacは下記のとおり。 使用マシンスペック ハードウェアの概要:機種名: MacBook Airプロセッサ...

my-studies.org

2022.06.06

C言語をパソコンにインストールしよう（Windows編）

なぜインストールが必要なのか Windowsパソコンを購入したあるいは、インストールした状態のままではC言語の開発環境はインストールされていない。ご自分でインストールする必要がある。C言語のテキストにはプログラムコードが掲載されているはずで...

my-studies.org

2022.05.26

ユークリッドの互除法によって最大公約数を求めるプログラム

//ユークリッドの互除法によって最大公約数を求めるプログラム

#include <stdio.h>

//整数値x,yの最大公約数を返却する
int gcd(int x,int y)
{
    if (y == 0)
        return x;
    else
        return gcd(y,x % y);
}

int main(void)
{
    int x,y;

    puts("二つの整数の最大公約数を求めます。");

    printf("整数を入力してください："); scanf("%d",&x);
    printf("整数を入力してください："); scanf("%d",&y);

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

    return 0;

}

実行結果

二つの整数の最大公約数を求めます。
整数を入力してください：22
整数を入力してください：8
最大公約数は2です。

二つの整数を長方形の2辺の長さとして、次のように考える。

長方形を正方形で埋めつくす。そのようにして作られる正方形の最大の辺の長さを求める

（例）22と8の最大公約数を求める。

１　図aの22cm×8cmの長方形を、短い辺の8cmの正方形に分割する。
　その結果、図bのように８cm×８cmの正方形が二つ埋まるが、８cm×6cmの長方形が残る。

２　残った８cm×6cmの長方形に対して、同じ手順の結果が図Cとなる。6cm×6cmの正方形が１個できて、6cm×2cmの長方形が残る。

３　残った6cm×2cmの長方形に対して、同じ手順の結果が図dとなる。2cm×2cmの正方形が３個埋まる。
→得られた２が最大公約数である。

この手続きを表現した関数が、gcd（ｘ、ｙ）である。（二つの整数xとyの最大公約数）

yが0であれば、x
そうでなければ、gcd(y,x % y)

（参考）新・解きながら学ぶC言語 第2版　柴田望洋 （監修・著）、 由梨かおる（著）SBクリエイティブ