C#でプロジェクトオイラーを解く（問題３「最大の素因数」）

Tweet

Pocket

どーも、みつおです。

この問題は手計算でできるのだろうか。

問題

3195 の素因数は 5, 7, 13, 29 である.

600851475143 の素因数のうち最大のものを求めよ.

出典：Problem 3

解答

using System;

namespace Problem3
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(Solve());
            Console.ReadLine();
        }

        private static long Solve()
        {
            long ret = 0;

            long num = 600851475143;

            //素因数分解した場合の最大値(平方根)を求める
            long root = (long)Math.Sqrt(num);

            //最大値から順に減少させていく
            for(long i = root; 0 < i; i--)
            {
                //割り切れるか判定
                if(num % i == 0)
                {
                    //素数か判定
                    if(IsSosu(i))
                    {
                        ret = i;
                        break;
                    }
                }
            }

            return ret;
        }

        private static bool IsSosu(long no)
        {
            bool ret = true;

            //数値が2未満なら素数じゃない、2なら素数
            if (no < 2) return false;
            else if (no == 2) return true;

            //数値が2で割り切れるなら素数じゃない
            if (no % 2 == 0) return false;

            //奇数でループ 
            for (int i = 3; i < no; i += 2)
            {
                //割り切れるので素数じゃない
                if (no % i == 0) return false;
            }

            return ret;
        }
    }
}

出力

6857