「アルゴリズム」カテゴリーアーカイブ

【C#】【アルゴリズム】最大公約数を求める(ユークリッドの互除法)

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

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

        /**
         * 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になったら操作を終了する。もう片方の数が最大公約数

というところ。

【C#】【アルゴリズム】約数を列挙する

値Nが持つ約数を列挙するアルゴリズムです。

        /**
         * 引数Nの約数をリストで返す
         * 
         * @param N 約数を求める値
         * @return Nの約数のリスト
         */
        public List<long> CalculateIsprimeList(long N)
        {
            List<long> list = new List<long>();
            for (long i = 2; i * i <= N; i++)
            {
                if (N % i != 0)
                {
                    continue;
                }
                list.Add(i);
                if(i != N / i)
                {
                    list.Add(N / i);
                }
            }

            list.Sort();
            return list;
        }

前回の素数判定のコードと似ています。

小さい値から、Nの約数を求めていき、約数だった場合、その値と商も約数として出力します。

【C#】【アルゴリズム】素数かどうかを判定するアルゴリズム

値Nが素数かどうかを判定するには、2~√Nで割り切れなければ素数らしい。

        /**
         * 引数Nが素数かどうかを判定する
         * 
         * @oaram N 素数判定する値
         * @return 素数:true/素数でない:false
         */

        public bool isprime(long N)
        {
            for(long i = 2; i * i <= N; i++)
            {
                if(N % i == 0)
                {
                    return false;
                }
            }
            return true;
        }