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

問題

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

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

ソース

#include <valarray>
#include <vector>
#include <string>
#include <stack>
#include <Windows.h>

const int Jyougen = 80;

std::vector<int> SosuuVect;

struct defineKeiro
{
    int GenzaiNode;
    int SumVal;
    std::string Path;
};

//エラトステネスの篩
void Eratosthenes()
{
    std::valarray<bool> IsSosuuArr(true,Jyougen);

    for (int I = 2; I * I <= (int)IsSosuuArr.size()-1; I++) {
        if(IsSosuuArr[I] == false) continue;
        for (int J = I * 2; J <= (int)IsSosuuArr.size()-1; J += I) {
            IsSosuuArr[J] = false;
        }
    }

    for (int I = 2; I <= (int)IsSosuuArr.size()-1; I++) {
        if(IsSosuuArr[I] == false) continue;
        SosuuVect.push_back(I);
    }
}

void main()
{
    Eratosthenes();

    for(int I = 2; I <= Jyougen; I++) {
        std::stack<defineKeiro> stk;
        defineKeiro WillPush;
        int CombiCnt = 0;

        std::vector<int> Graph;
        for(std::vector<int>::iterator it = SosuuVect.begin();it!=SosuuVect.end();it++){
            if(*it <= I) Graph.push_back(*it);
        }

        for (int J=0;J<=(int)Graph.size()-1;J++){
            WillPush.GenzaiNode = J;
            WillPush.SumVal = Graph.at(J);
            char wkCharArr[100]; wsprintf(wkCharArr,"%d",Graph.at(J));
            WillPush.Path = wkCharArr;
            stk.push(WillPush);
        }

        while(stk.empty() == false){
            defineKeiro Popped = stk.top(); stk.pop();

            if (Popped.SumVal == I) {
                printf("和が%dの素数の組合せ%d=%s\n",I,++CombiCnt, Popped.Path.c_str());
                continue;
            }

            if (Popped.SumVal > I) continue;

            for (int J = Popped.GenzaiNode; J<=(int)Graph.size()-1;J++){
                WillPush.GenzaiNode = J;
                WillPush.SumVal = Popped.SumVal + Graph.at(J);
                WillPush.Path = Popped.Path + ",";
                char wkCharArr[100];wsprintf(wkCharArr,"%d",Graph.at(J));
                WillPush.Path += wkCharArr;
                stk.push(WillPush);
            }
        }
        if (CombiCnt >= 5000) return;
    }
}

実行結果

省略
和が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,3,3,5
和が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,3,3,3
和が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,7
和が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,5
和が71の素数の組合せ5007=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

解説

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