Project Euler : Problem 46 『Goldbach's other conjecture』

問題

projecteuler.net
日本語訳→Problem 46 - PukiWiki

25の場合

　例にあるように25の場合は
となっている。
25を奇合成数、7を素数、その他を2×平方数と置くと

このように書ける。

　これが成立しない最小の奇合成数を探すということで、
0)ある奇合成数Numを用意する
1)平方数の元の数s(最初は1)を用意する
2)Numから2×s×sを引く
3)引いた結果が素数になってるかどうか判定
4)sを1,2,3…まで変えていき、都度素数判定する
5)一度でも素数判定okになれば次のNumを用意する
6)最後まで素数判定に引っかからなければ、それが最小の奇合成数
こんな感じでやっていく。

コード

using System;
using System.Diagnostics;

namespace Problem46
{
    class Program
    {
        static void Main(string[] args)
        {
            //33までは成立する(既知)
            var num = 33;

            //ゴールドバッハの予想が失敗するまで探索
            while (IsGoldbachConjecture(num) == true)
            {
                num = NextOddCompositeNumber(num);
            }
        }

        /// <summary>
        /// 次の奇合成数を探す(奇数＆非素数)
        /// </summary>
        /// <param name="num">現在の奇合成数</param>
        /// <returns>次の奇合成数</returns>
        static int NextOddCompositeNumber(int num)
        {
            do
            {
                num += 2;
            } while (IsPrime(num) == true);

            return num;
        }

        /// <summary>
        /// ゴールドバッハの予想
        /// </summary>
        /// <param name="num">調べる数</param>
        /// <returns>true:成立 false:不成立</returns>
        static bool IsGoldbachConjecture(int num)
        {
            //調べる平方数の最大値を得る
            var c = Math.Sqrt(num / 2);

            //検査値から平方数*2を引いた値が素数かどうか判定する
            for (int i = 1; i < c; i++)
            {
                var n = num - 2 * i * i;

                if (IsPrime(n) == true) return true;
            }

            //ゴールドバッハの予想の反例発見
            Debug.WriteLine(num);
            return false;
        }

        /// <summary>
        /// 素数判定
        /// </summary>
        /// <param name="n">検査する数</param>
        /// <returns>true:素数 false:非素数</returns>
        static bool IsPrime(int num)
        {
            //2以下は素数ではない
            if (num <= 2) return false;
            //偶数は素数ではない
            if (num % 2 == 0) return false;

            //ルートn以下の奇数で割れるなら素数ではない
            var c = Math.Sqrt(num);

            for (int i = 3; i <= c; i += 2)
            {
                if (num % i == 0) return false;
            }

            //おめでとう。君は素数だ
            return true;
        }
    }
}

答え

5777

　案外小さい数だった

田中貴金属ゴールドバー 100g 田中貴金属発行 100gの純金 24金 ゴールド インゴット

ニュー・ベスト・バッハ100

動画で見る競馬予想