Problem46 もうひとつのゴールドバッハの予想

問題

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

 9 =  7 + (1*1)*2
15 =  7 + (2*2)*2
21 =  3 + (3*3)*2
25 =  7 + (3*3)*2
27 = 19 + (2*2)*2
33 = 31 + (1*1)*2

後に, この予想は誤りであることが分かった.
平方数の2倍と素数の和で表せない最小の奇合成数はいくつか?

ソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    const int Jyougen = 10000;

    static int[] SosuuArr = new int[Jyougen + 1];

    //エラトステネスの篩
    static void Eratosthenes()
    {
        for (int I = 2; I <= SosuuArr.GetUpperBound(0); I++) {
            SosuuArr[I] = I;
        }
        for (int I = 2; I * I <= SosuuArr.GetUpperBound(0); I++) {
            if (I != 2 && I % 2 == 0) continue;

            if (SosuuArr[I] != 0) {
                for (int J = I * 2; J <= SosuuArr.GetUpperBound(0); J += I) {
                    SosuuArr[J] = 0;
                }
            }
        }
        SosuuArr = SosuuArr.Where(X => X != 0).ToArray();
    }

    static void Main()
    {
        Eratosthenes();

        var KigouseisuuSet = new HashSet<int>();

        //合成数は、自然数で、1とその数自身以外の約数を持つ数
        Predicate<int> IsKigouseisuu = (pTarget) =>
        {
            if (pTarget % 2 == 0) return false;

            for (int I = 2; I * I <= pTarget; I++) {
                if (pTarget % I == 0) return true;
            }
            return false;
        };

        for (int I = 1; I <= Jyougen; I++) {
            if (IsKigouseisuu(I))
                KigouseisuuSet.Add(I);
        }

        for (int I = 1; 2 * I * I <= Jyougen; I++) {
            foreach (int EachSosuu in SosuuArr) {
                int wkInt = EachSosuu + 2 * I * I;
                if (Jyougen < wkInt) break;
                KigouseisuuSet.Remove(wkInt);
            }
        }

        Console.WriteLine("{0}以下の奇合成数で検証します", Jyougen);
        Console.WriteLine("Answer={0}", KigouseisuuSet.Min());
    }
}

実行結果

10000以下の奇合成数で検証します
Answer=5777

解説

HashSetクラスを使って、候補となる数値を管理してます。
MSDN --- HashSet