Problem77 素数の和での表し方が5000通り以上になる最初の数

問題

10は素数の和として5通りに表すことができる:

7 + 3
5 + 5
5 + 3 + 2
3 + 3 + 2 + 2
2 + 2 + 2 + 2 + 2
素数の和としての表し方が5000通り以上になる最初の数を求めよ。

ソース

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

class Program
{
    const int Jyougen = 80;
    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();
    }

    struct JyoutaiDef
    {
        internal int CurrInd;
        internal int SumVal;
        internal string Path;
    }

    static void Main()
    {
        Eratosthenes();

        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;

        for (int I = 2; I <= Jyougen; I++) {
            int CombiCnt = 0;
            Stk.Clear();
            int[] Graph = SosuuArr.Where(X => X <= I).ToArray();

            for (int J = 0; J <= Graph.GetUpperBound(0); J++) {
                if (Graph[J] >= I) break;

                WillPush.CurrInd = J;
                WillPush.SumVal = Graph[J];
                WillPush.Path = Graph[J].ToString();
                Stk.Push(WillPush);
            }

            while (Stk.Count > 0) {
                JyoutaiDef Popped = Stk.Pop();

                if (Popped.SumVal == I) {
                    Console.WriteLine("和が{0}の素数の組合せ{1}={2}", I, ++CombiCnt, Popped.Path);
                    continue;
                }

                for (int J = Popped.CurrInd; J <= Graph.GetUpperBound(0); J++) {
                    WillPush.CurrInd = J;
                    WillPush.SumVal = Popped.SumVal + Graph[J];

                    if (WillPush.SumVal > I) break;

                    WillPush.Path = Popped.Path + "," + Graph[J].ToString();
                    Stk.Push(WillPush);
                }
            }
            if (CombiCnt >= 5000) return;
        }
    }
}

実行結果

省略
和が71の素数の組合せ5000=2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,3,7
和が71の素数の組合せ5001=2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,11
和が71の素数の組合せ5002=2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,3,5
和が71の素数の組合せ5003=2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,3,3
和が71の素数の組合せ5004=2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,7
和が71の素数の組合せ5005=2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,5
和が71の素数の組合せ5006=2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3

解説

エラトステネスの篩を使ってから、
深さ優先探索してます。

深さ優先探索の代わりに、動的計画法を使ってもいいです。