WEBサービス創造記

WEBサービスを作ったり保守したりしてる人のメモブログです。

最大公約数の算出

      2014/11/17

約数とはnを余ることなく割り切ることができる整数のことです(因数・因子などと呼ばれることもあるそうです)。
整数 n が整数 m の約数であることを、記号 | を用いて n | m と表すようです。

例えば、4は2で余りを出すことなく割り切れるので、2は4の約数と言えます。
2 | 4

公約数とは2つ(以上)の整数に共通した約数のことです。
24と36はそれぞれ6で割り切れるので、公約数は6となります。また6以外でも12や2、3などの数でも割り切れるのでこれらも公約数となります。
このように複数の公約数の中で最大の約数のことを最大公約数と呼びます(24と36の例だと最大公約数は12)。

最大公約数は2つの数(この例だと24と36)の約数を羅列し、それを掛けあわせて算出します。24と36のような簡単な例では勘でどちらも12や6で割り切れるとわかるので、簡単に最大公約数を計算できることがほとんどです。
人間の勘や判断を利用してではなく、より論理的に(機械的に)最大公約数を算出する手法にユークリッドの互除法というものがあります。

ユーグリッドの互除法には除算を使う方法と減算を使う方法の二通りがありますが、ここではわかりやすそうな減算を使う方法を用います。
まず、最大公約数を求めたい2つの数で、大きい方から小さい方を引くことを2つの数の値が同じになるまで繰り返します。

C言語によるアルゴリズムで表すと以下のような感じになります。

#include <stdio.h>

int main(void)
{
    int a;
    int b;
    int result;

    printf("最大公約数を算出したい整数を2つ入力してください。¥n");
    scanf("%d", &a);
    scanf("%d", &b);

    while (a != b) {
        if (a > b) {
            a = a - b;
        } else {
            b = b - a;
        }
    }

    printf("最大公約数は%dです。¥n", b);
}

なお、最大公約数の約数=すべての公約数ということになるので、最大公約数を求めればすべての公約数を知ることができます。

 - 数学 , , ,