ユークリッド互除法

アルゴリズム
ユークリッド互除法
ユークリッドの互除法(ユークリッドのごじょほう、英: Euclidean Algorithm)は、2 つの自然数の最大公約数を求める手法の一つである。

2 つの自然数 a, b (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に等しいという性質が成り立つ。この性質を利用して、 b を r で割った剰余、 除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が a と b との最大公約数となる。


実際に計算してみる


ロジック自体はものすごく単純です。実際の計算をみてみましょう。
280 = 2 * 2 * 2 * 5 * 7
945 = 3 * 3 * 3 * 5 * 7
つまり最大公約数は5 * 7の35です。

945 / 280 = 3あまり105
945の代わりに105に置き換え
-----------------------------------
280 = 2 * 2 * 2 * 5 * 7
105 = 3 * 5 * 7
-----------------------------------
280 / 105 = 2あまり70
280の代わりに70に置き換え
-----------------------------------
70 = 2 * 5 * 7
105 = 3 * 5 * 7
-----------------------------------
105 / 70 = 1あまり35
105の代わりに35に置き換え
-----------------------------------
70 = 2 * 5 * 7
35 = 5 * 7
-----------------------------------
70 / 35 = 2あまり0
よって35が最大公約数。

ロジック自体は単純なのですが、
なぜそれで、求まるかというと。

求まる理由


(i)a = bの場合
aとbが同じ値のため、それが最大公約数になる。

(ii)a < b の場合
もし、aをq倍した値と一致するのであれば、aが最大公約数になる。
b = q * a

実際は、aをq倍して何かを足した状態になっているので
aとbの関係は b = q * a + r となる。
r = 0の時が最小公倍数が求まったときである。

最大公約数をgとすると、aもbも共にそれぞれ最大公約数を何倍かした値である。
先ほどの例をあげるとa=280, b=945
280 = 8 * 35
945 = 27 * 35

a(280)が最大公約数を何倍かした値であるなら、それをq倍した値も最大公約数を何倍かした値ということになる。
945 = 3 * 280 + 105
945 = 3 * (8 * 35) + 105
945 = 24 * 35 + 105

945は、最小公倍数である35を24倍した値に105を足したものである。
945は、35を27倍したものなので、105は、35を3倍したものということになる。
945 = 24 * 35 + 3 * 35 = 27 * 35

つまり、あまりにも最小公倍数が含まれるため、
大きい方の値をあまりに置き換えることができる。

以上のことから、大きい方の値を小さい方でわり、あまりを求め
大きい方の値をあまりに置き換え、それらの処理を繰り返していき、あまりが0になった時が最大公約数が求まった時になる。

using System;

namespace Sample
{
    class Program
    {
        static void Main()
        {
            var ret = GreatestCommonDivisor(280, 945);
            Console.WriteLine(ret);
        }

        static int GreatestCommonDivisor(int num1, int num2)
        {
            do
            {
                if (num1 <= num2)
                {
                    num2 %= num1;
                }
                else
                {
                    num1 %= num2;
                }
            } while (0 != num1 * num2);

            return (0 < num1) ? num1 : num2;
        }
    }
}


こっちの方がシンプルかな。
using System;

namespace Sample
{
    class Program
    {
        static void Main()
        {
            var ret = GreatestCommonDivisor(945, 280);
            Console.WriteLine(ret);
        }

        static int GreatestCommonDivisor(int a, int b)
        {

            if (b < a)
            {
                var temp = a;
                a = b;
                b = temp;
            }

            var r = 0;
            do
            {
                r = b % a;
                b = a;
                a = r;
            } while (0 < r);

            return b;
        }
    }
}

投稿日時: 2019-12-02 16:00:02
更新日時: 2019-12-05 00:07:05
バブルソート | macのデフォルトのshell

Comment