Problem87 素数の2乗と素数の3乗と素数の4乗の和で表される数

問題

素数の2乗と素数の3乗と素数の4乗の和で表される最小の数は28である.
50未満のこのような数は丁度4つある.

28 = 2の2乗 + 2の3乗 + 2の4乗
33 = 3の2乗 + 2の3乗 + 2の4乗
49 = 5の2乗 + 2の3乗 + 2の4乗
47 = 2の2乗 + 3の3乗 + 2の4乗
では, 5000万未満の数で, 素数の2乗と素数の3乗と素数の4乗の和で表される数は何個あるか?

ソース

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

class Program
{
    //const int SikiiVal = 50;
    const int SikiiVal = 50000000;
    static int[] SosuuArr = new int[SikiiVal];

    //エラトステネスの篩
    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 && (long)X * X < SikiiVal).ToArray();
    }

    static void Main()
    {
        Eratosthenes();

        var List2Jyou = new List<int>();
        var List3Jyou = new List<int>();
        var List4Jyou = new List<int>();

        for (int I = 0; I <= SosuuArr.GetUpperBound(0); I++) {
            if ((long)SosuuArr[I] * SosuuArr[I] <= SikiiVal) {
                List2Jyou.Add(SosuuArr[I] * SosuuArr[I]);
            }
            else break;

            if ((long)SosuuArr[I] * SosuuArr[I] * SosuuArr[I] <= SikiiVal) {
                List3Jyou.Add(SosuuArr[I] * SosuuArr[I] * SosuuArr[I]);
            }
            if ((long)SosuuArr[I] * SosuuArr[I] * SosuuArr[I] * SosuuArr[I] <= SikiiVal) {
                List4Jyou.Add(SosuuArr[I] * SosuuArr[I] * SosuuArr[I] * SosuuArr[I]);
            }
        }

        int[] Arr2Jyou = List2Jyou.ToArray<int>();
        int[] Arr3Jyou = List3Jyou.ToArray<int>();
        int[] Arr4Jyou = List4Jyou.ToArray<int>();

        bool[] IsAppearArr = new bool[SikiiVal];

        for (int I = 0; I <= Arr4Jyou.GetUpperBound(0); I++) {
            long SumVal = Arr4Jyou[I];
            if (SikiiVal < SumVal) break;

            for (int J = 0; J <= Arr3Jyou.GetUpperBound(0); J++) {
                SumVal = (long)Arr4Jyou[I] + Arr3Jyou[J];
                if (SikiiVal < SumVal) break;

                for (int K = 0; K <= Arr2Jyou.GetUpperBound(0); K++) {
                    SumVal = (long)Arr4Jyou[I] + Arr3Jyou[J] + Arr2Jyou[K];
                    if (SikiiVal < SumVal) break;
                    IsAppearArr[SumVal] = true;
                }
            }
        }
        int AnsCnt = 0;
        for (int I = 0; I <= IsAppearArr.GetUpperBound(0); I++) {
            if (IsAppearArr[I]) {
                Console.WriteLine("{0}個目の解は{1}", ++AnsCnt, I);
            }
        }
    }
}

実行結果

省略
1097340個目の解は49999665
1097341個目の解は49999849
1097342個目の解は49999891
1097343個目の解は49999927

解説

Bool型の配列で存在有無を管理してます。