Problem50 100万未満の素数を連続する素数の和で表す

問題

素数41は6つの連続する素数の和として表せる:

41 = 2 + 3 + 5 + 7 + 11 + 13
100未満の素数を連続する素数の和で表したときにこれが最長になる.

同様に, 連続する素数の和で1000未満の素数を表したときに最長になるのは953で21項を持つ.

100万未満の素数を連続する素数の和で表したときに最長になるのはどの素数か?

ソース

#include <valarray>
#include <vector>
#include <algorithm>
#include <stdio.h>

//const int MaxVal =  100 - 1;
//const int MaxVal = 1000 - 1;
const int MaxVal = 1000000 - 1;

std::vector<int> SosuuVect;

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

    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();

    int SaveSumVal = 0;
    int MaxKousuu = 0;

    int SosuuVectUB = (int)SosuuVect.size()-1;
    for (int I = 0; I <= SosuuVectUB; I++) {
        if ((int)SosuuVect.size()-I+1 < MaxKousuu) break;
        if (SosuuVect.at(I)*2 > MaxVal) break;

        int SumVal = 0;
        int KariMaxKousuu = 0;

        for (int J = I; J <= SosuuVectUB; J++) {
            SumVal += SosuuVect.at(J);
            if (SumVal > SosuuVect.at(SosuuVectUB)) break;
            KariMaxKousuu++;

            if(std::binary_search(SosuuVect.begin(),SosuuVect.end(),SumVal)){
                if (MaxKousuu < KariMaxKousuu) {
                    SaveSumVal = SumVal;
                    MaxKousuu = KariMaxKousuu;
                }
            }
        }
    }
    printf("%dで最大項数=%d\n",SaveSumVal, MaxKousuu);
}

実行結果

997651で最大項数=543

解説

if文とbreak文による、3つの打ち切り条件を仕掛けてあります。