二つの値の最大公約数を求めるアルゴリズムです。

まともに計算すると時間が掛かるので、ユークリッドの互除法というアルゴリズムを使用します。

        /**
         * AとBの最大公約数を求める(ユークリッドの互除法)
         * 
         * @param A 最大公約数を求める対象の値A
         * @param B 最大公約数を求める対象の値B
         * @return AとBの最大公約数
         */
        public long GreatestCommonDivisor(long A, long B)
        {
            while(A >= 1 && B >= 1)
            {
                if(A < B)
                {
                    B = B % A;
                }
                else
                {
                    A = A % B;
                }
            }
            if(A >= 1)
            {
                return A;
            }
            return B;
        }

ポイントは、

・大きい方の数を「大きい方を小さい方で割った余り」に書き換える処理を繰り返す

・片方が0になったら操作を終了する。もう片方の数が最大公約数

というところ。