最大公約数

こんばんは

今日は最大公約数を求めるプログラムを作ってきました

ユークリッドの互除法を用いて最大公約数を求めます。

ユークリッドの互除法というのは、「自然数 a、b (a > b) について、aとbの剰余をrとすると、aとbの最大公約数はbとrの最大公約数に等しい」というものです。

この処理を繰り返していき、剰余が0になったところが最大公約数になります。

詳しい説明はいくらでもWeb上に上がっているので、そちらを見てください

以下が2つの整数の最大公約数を求めるプログラムです。

#include <stdio.h>

int gcd(int x,int y);

int gcd(int x,int y){
    int r,tmp;
    
    /*値の大きい方をxとする*/
    if( x < y ){
        tmp = x;
        x = y;
        y = tmp;
    }
    
    /*どちらかの値が0の場合は0を返す*/
    if( !x || !y ){
        return 0;
    } else {
        /*ユークリッドの互除法*/
        r = x % y;
        while( r ){
            x = y;
            y = r;
            r = x % y;
        }
        return y;
    }
}

int main(void){
    int a,b;
    
    printf("整数を2つ入力してください\n");
    scanf("%d",&a);
    scanf("%d",&b);
    
    /*最大公約数を出力*/
    printf("最大公約数は %d\n",gcd(a,b));
    return 0;
}

また、このgcd関数を利用して、3個の整数の最大公約数を求めるプログラムを作りました。

main関数だけ載せておきます。gcd関数の中身は何も変わっていません。

int main(void){
    int a,b,c;
    
    printf("整数を3つ入力してください\n");
    scanf("%d",&a);
    scanf("%d",&b);
    scanf("%d",&c);
    
    /*最大公約数を出力*/
    printf("最大公約数は %d\n",gcd(gcd(a,b),c));
    return 0;
}
 

整数の数がいくつに増えても最大公約数が求まると思います。

『今日のどうでもいいこと』

シャーペン　より鉛筆　のほうがなんとなくスキ

本日は以上です。

おやすみなさい