C#でプロジェクトオイラーを解く（問題４６「もうひとつのゴールドバッハの予想」）

Tweet

Pocket

どーも、みつおです。

問題

Christian Goldbachは全ての奇合成数は平方数の2倍と素数の和で表せると予想した.

9 = 7 + 2×1^2
15 = 7 + 2×2^2
21 = 3 + 2×3^2
25 = 7 + 2×3^2
27 = 19 + 2×2^2
33 = 31 + 2×1^2

後に, この予想は誤りであることが分かった.

平方数の2倍と素数の和で表せない最小の奇合成数はいくつか?

出典：Problem46

解答

using System;

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

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

            //奇数でループ
            while(true)
            {
                i += 2;

                //奇合成数か判定（素数じゃなければ、奇合成数）
                if(!IsSosu(i))
                {
                    //奇合成数 = 素数 + 2 * x * x　で表せるか判定
                    if (!IsHeiho(i))
                    {
                        ret = i;
                        break;
                    }
                }
            }

            return ret;
        }

        private static bool IsHeiho(long no)
        {
            bool ret = false;
            int x = 1;
            long num = 0;

            while(true)
            {
                //奇合成数 = 素数 + 2 * x * x を 移行　素数 = 奇合成数 - 2 * x * x
                num = no - 2 * x * x;

                //マイナスの値になれば終了
                if (1 < num)
                {
                    //素数か判定
                    if (IsSosu(num)) return true;
                }
                else break;

                //項をインクリメント
                x++;
            }

            return ret;
        }

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

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

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

            //合成数xはp≦√xを満たす素因子pをもつ
            double sqrtno = Math.Sqrt(no);

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

            return ret;
        }
    }
}

出力

5777