Problem47 連続する4つの数がそれぞれ4つの異なる素因数

問題

連続する2つの数がそれぞれ2つの異なる素因数を持つのは
    14 = 2*7
    15 = 3*5 の場合である

同様に連続する3つの数がそれぞれ3つの異なる素因数を持つのは
    644 = 2の2乗*7*23
    645 = 3*5*43
    646 = 2*17*19 の場合である

連続する4つの数がそれぞれ4つの異なる素因数を持つ場合を考え、連続する数の中で最小のものを答えよ

ソース

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

//const int NeedPair = 2;
//const int NeedPair = 3;
const int NeedPair = 4;

const int Jyougen = 135000;

std::vector<int> SosuuVect;

std::vector<int> DeriveSoinsuuVect(int pTarget);

//エラトステネスの篩
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();

    std::map<int,std::vector<int> > SoinsuuBunkaiMap;

    for (int I = 2; I <= Jyougen; I++) {
        std::vector<int> SoinsuuVect = DeriveSoinsuuVect(I);

        char wkCharArr[100];wsprintf(wkCharArr,"%dの素因数は",I);
        std::string WillOut = wkCharArr;

        for(std::vector<int>::iterator it = SoinsuuVect.begin();it!=SoinsuuVect.end();it++){
            wsprintf(wkCharArr,"%d,",*it);
            WillOut += wkCharArr;
        }
        printf("%s\n",WillOut.c_str());

        SoinsuuBunkaiMap.insert(std::pair<int,std::vector<int> > (I,SoinsuuVect));
        if (SoinsuuBunkaiMap[I].size() == NeedPair
         && SoinsuuBunkaiMap.size() >= NeedPair) {
             bool IsOK = true;
             for (int J=I-NeedPair+1 ; J<=I-1 ; J++) {
                 if (SoinsuuBunkaiMap[J].size() != NeedPair) {
                     IsOK = false;
                     break;
                 }
             }
             if (IsOK) {
                 printf("Answer=%d\n",I-NeedPair+1);
                 return;
             }
        }
        if (I % 10000 == 0) { //Mapから不要になったキーをerase
            std::map<int,std::vector<int> >::iterator endIt = SoinsuuBunkaiMap.end();
            std::advance(endIt, -NeedPair);
            SoinsuuBunkaiMap.erase(SoinsuuBunkaiMap.begin(),endIt);
        }
    }
}

std::vector<int> DeriveSoinsuuVect(int pTarget)
{
    std::vector<int> SoinsuuVect;
    if(std::binary_search(SosuuVect.begin(),SosuuVect.end(),pTarget)){
        SoinsuuVect.push_back(pTarget);
        return SoinsuuVect;
    }

    for(std::vector<int>::iterator it=SosuuVect.begin();it!=SosuuVect.end();it++){
        bool FirstFlag = true;
        while (pTarget % (*it) == 0) {
            if (FirstFlag) {
                FirstFlag = false;
                SoinsuuVect.push_back(*it);
            }
            pTarget /= (*it);
        }
        if (pTarget == 1) break;
    }
    return SoinsuuVect;
}

実行結果

省略
134041の素因数は311,431,
134042の素因数は2,67021,
134043の素因数は3,7,13,491,
134044の素因数は2,23,31,47,
134045の素因数は5,17,19,83,
134046の素因数は2,3,11,677,
Answer=134043

解説

Mapコンテナで素因数分解の結果をキャッシュしつつ、
eraseメソッドで不要になったキーをeraseしてます。

MSDN --- map::erase