Problem60 任意の2つの素数を繋げても素数な、5つの素数の組

問題

素数3, 7, 109, 673は非凡な性質を持っている.
任意の2つの素数を任意の順で繋げると, また素数になっている.

例えば, 7と109を用いると, 7109と1097の両方が素数である.
これら4つの素数の和は792である.
これは, このような性質をもつ4つの素数の組の和の中で最小である.

任意の2つの素数を繋げたときに別の素数が生成される, 5つの素数の組の和の中で最小のものを求めよ.

ソース

#include <valarray>
#include <vector>
#include <string>
#include <stack>
#include <Windows.h>
#include <stdio.h>
#include <numeric>
#include <algorithm>
#include <functional>

//const int CombinationCnt = 4;
//const int Jyougen = 800;
const int CombinationCnt = 5;
const int Jyougen = 27000;

std::vector<int> SosuuVect;

bool IsSosuu(__int64 pVal);
__int64 DeriveConcatVal(int pLeft, int pRight);

//エラトステネスの篩
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);
    }
    std::sort(SosuuVect.begin(),SosuuVect.end(), std::greater<int>());
}

struct JyoutaiDef
{
    std::vector<int> ValVect;
    std::string Path;
};

void main()
{
    Eratosthenes();

    std::stack<JyoutaiDef> stk;
    JyoutaiDef WillPush;
    for(std::vector<int>::iterator it=SosuuVect.begin();it!=SosuuVect.end();it++){
        WillPush.ValVect = std::vector<int>(1,*it);
        char wkCharArr[100];wsprintf(wkCharArr,"%d,",*it);
        WillPush.Path = wkCharArr;
        stk.push(WillPush);
    }

    std::string AnswerPath;
    int AnswerSumMin = Jyougen;

    while(stk.empty() == false){
        JyoutaiDef Popped = stk.top(); stk.pop();
        printf("Path=%s 解候補=%s\n",Popped.Path.c_str(),AnswerPath.c_str());

        int wkSum = std::accumulate(Popped.ValVect.begin(),Popped.ValVect.end(),0);

        if (Popped.ValVect.size() == CombinationCnt && wkSum < AnswerSumMin) {
            AnswerSumMin = wkSum;
            AnswerPath = Popped.Path;
            continue;
        }

        int ValCnt = Popped.ValVect.size();
        int RestCnt = CombinationCnt - ValCnt;

        int LastVal = Popped.ValVect.at(ValCnt - 1);
        for(std::vector<int>::iterator it=SosuuVect.begin();it!=SosuuVect.end();it++){
            if(! (*it > LastVal && AnswerSumMin > wkSum + *it * RestCnt) ) continue;

            bool wkBool = true;
            for(int I=0;I<=(int)Popped.ValVect.size()-1;I++){
                if(IsSosuu(DeriveConcatVal(Popped.ValVect.at(I),*it)) == false
                || IsSosuu(DeriveConcatVal(*it,Popped.ValVect.at(I))) == false){
                    wkBool = false;
                    break;
                }
            }
            if (wkBool == false) continue;

            WillPush.ValVect = Popped.ValVect;
            WillPush.ValVect.push_back(*it);
            WillPush.Path = Popped.Path;
            char wkCharArr[100];wsprintf(wkCharArr,"%d,",*it);
            WillPush.Path += wkCharArr;
            stk.push(WillPush);
        }
    }
    printf("%d以下の素数の組み合わせで検証しました。\n",Jyougen);

    int MaxVal=INT_MIN;
    for(int I=0;I<=(int)SosuuVect.size()-1;I++)
        if(MaxVal < SosuuVect.at(I)) MaxVal = SosuuVect.at(I);
    printf("%d以下の素数の最大値は%dです。\n",Jyougen,MaxVal);

    printf("解は%sで和は%dです。\n",AnswerPath.c_str(),AnswerSumMin);
}

bool IsSosuu(__int64 pVal)
{
    if (pVal <= Jyougen)
        return std::find(SosuuVect.begin(),SosuuVect.end(),(int)pVal) != SosuuVect.end();

    if (pVal % 2 == 0) return false;
    for (int I = 3; I * I <= pVal; I += 2) {
        if (pVal % I == 0) return false;
    }
    return true;
}

__int64 DeriveConcatVal(int pLeft, int pRight)
{
    __int64 WillReturn = pLeft;
    if (pRight < 10) WillReturn *= 10; //1桁の場合
    else if (pRight < 100) WillReturn *= 100; //2桁の場合
    else if (pRight < 1000) WillReturn *= 1000; //3桁の場合
    else if (pRight < 10000) WillReturn *= 10000; //4桁の場合
    else if (pRight < 100000) WillReturn *= 100000; //5桁の場合

    WillReturn += pRight;
    return WillReturn;
}

実行結果

省略
Path=26951, 解候補=13,5197,5701,6733,8389,
Path=26953, 解候補=13,5197,5701,6733,8389,
Path=26959, 解候補=13,5197,5701,6733,8389,
Path=26981, 解候補=13,5197,5701,6733,8389,
Path=26987, 解候補=13,5197,5701,6733,8389,
Path=26993, 解候補=13,5197,5701,6733,8389,
27000以下の素数の組み合わせで検証しました。
27000以下の素数の最大値は26993です。
解は13,5197,5701,6733,8389,で和は26033です。

解説

深さ優先探索で早く解候補を求めて、枝切り条件に使用してます。

枝切りでは、
素数の昇順になる組み合わせでチェックしているので
解候補の和を超える素数の組み合わせを枝切りしてます。

素数の和の上限を27000と仮決めした上で、
27000以下の素数の組み合わせで検証して
求まった解の合計が26033で
27000 > 26033 なので、5つの素数の組の和の中で最小のものという題意を満たしてます :-)
反復深化で素数の上限を増やしていくほうが、
解答としては優れているかもしれません :-)