Problem37 切り詰めても素数になる数の総和

問題

3797は面白い性質を持っている. まずそれ自身が素数であり,
左から右に桁を除いたときに全て素数になっている(3797, 797, 97, 7).
同様に右から左に桁を除いたときも全て素数である(3797, 379, 37, 3).

右から切り詰めても左から切り詰めても素数になるような素数は11個しかない.総和を求めよ.

注: 2, 3, 5, 7を切り詰め可能な素数とは考えない.

ソース

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

std::vector<int> SosuuVect;

const int Jyougen = 740000;

//エラトステネスの篩
void Eratosthenes()
{
    std::valarray<bool> IsSosuuArr(true,Jyougen+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 SumVal=0,Rest=11;
    for (int I = 0; I <= (int)SosuuVect.size()-1; I++) {
        if (SosuuVect.at(I) < 10) continue;
        bool IsOK = true;
        for (int J = 10; J <= SosuuVect.at(I); J *= 10) {
            if (std::binary_search(SosuuVect.begin(),SosuuVect.end(),SosuuVect.at(I)/J) == false){
                IsOK = false;break;
            }
            if (std::binary_search(SosuuVect.begin(),SosuuVect.end(),SosuuVect.at(I)%J) == false){
                IsOK = false;break;
            }
        }
        if (IsOK) {
            printf("%7d,SumVal=%7d\n",SosuuVect.at(I),SumVal+=SosuuVect.at(I));
            if (--Rest == 0) return;
        }
    }
}

実行結果

     23,SumVal=     23
     37,SumVal=     60
     53,SumVal=    113
     73,SumVal=    186
    313,SumVal=    499
    317,SumVal=    816
    373,SumVal=   1189
    797,SumVal=   1986
   3137,SumVal=   5123
   3797,SumVal=   8920
 739397,SumVal= 748317

解説

型を変更しないように、10の乗数での剰余や商を求めてます。