Problem35 100万未満の巡回素数は何個か?

問題

197は巡回素数と呼ばれる. 桁を回転させたときに得られる数 197, 971, 719 が全て素数だからである.

100未満には巡回素数が13個ある: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, および97である.
100万未満の巡回素数は何個か?

ソース

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

std::vector<int> SosuuVect;

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

    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();
    //const int SikiiVal = 100;
    const int SikiiVal = 1000000;

    std::vector<int>::iterator wkIt = std::lower_bound(SosuuVect.begin(),SosuuVect.end(),SikiiVal);
    SosuuVect.erase(wkIt,SosuuVect.end());

    int cnt = 0;
    for (int I = 0; I <= (int)SosuuVect.size()-1; I++) {
        bool IsOK = true;
        char wkCharArr[100]; wsprintf(wkCharArr,"%d",SosuuVect.at(I));
        const int wkCharArrUB = (int)strlen(wkCharArr)-1;
        for (int J = 0; J <= wkCharArrUB; J++) {
            std::string WillCastInt;
            for (int K = 0; K <= wkCharArrUB; K++) {
                int wkP = J + K;
                if (wkP > wkCharArrUB) wkP -= wkCharArrUB + 1;
                WillCastInt += wkCharArr[wkP];
            }
            if(std::binary_search(SosuuVect.begin(),SosuuVect.end(),atoi(WillCastInt.c_str()))==false){
                IsOK = false;
                break;
            }
        }
        if(IsOK) printf("%dは%d番目の巡回素数\n",SosuuVect.at(I),++cnt);
    }
}

実行結果

省略
933199は51番目の巡回素数
939193は52番目の巡回素数
939391は53番目の巡回素数
993319は54番目の巡回素数
999331は55番目の巡回素数

解説

2ではなく2を含んでいたら除外する。
5ではなく5を含んでいたら除外する。
といったフィルタを素数リストに行ってもいいかもしれません。