プロジェクトオイラー Problem 60 「素数ペア集合」 †

Problem 60 「素数ペア集合」 †

素数3, 7, 109, 673は非凡な性質を持っている. 任意の2つの素数を任意の順で繋げると, また素数になっている. 例えば, 7と109を用いると, 7109と1097の両方が素数である. これら4つの素数の和は792である. これは, このような性質をもつ4つの素数の集合の和の中で最小である.

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

解法
とりあえず上限を定めて全探索した結果暫定的な答えを得ました。
暫定解よりも大きな素数が答えの5つの数字に入らないことは明白なので。
その上限で全探索して答えを確認すればよいですが。
高速化の方法がわかりません。




#include<stdio.h>
#include<vector>
#include<map>
#include<set>
#include<string.h>
#include<iostream>

const int PRIME_LIMIT=100000;
const int SEARCH_LIMIT=27000;

std::map<__int64,std::set<__int64> > cons;
std::vector<__int64> primes,set5;
__int64 ans=-1;



bool isConnectOK(__int64 a,__int64 b){
      __int64 mult=1,c,d;
      while(mult<=b)mult*=10;
      c=a*mult+b;
      for(int i=0;i<primes.size();i++){
            d=primes[i];
            if(c<d*d)break;
            if(c%d==0)return false;
      }
      return true;
}

void search5(std::set<__int64>::iterator &it,std::set<__int64>::iterator &eIt,__int64 sum){
      if(ans!=-1&&(ans<sum||SEARCH_LIMIT<sum))return ;
      if(set5.size()==5){
            if(ans==-1||sum<ans)ans=sum;
            for(int i=0;i<5;i++){
                  std::cout<<set5[i]<<" ";
            }
            std::cout<<sum<<"\n";
      }else if(it==eIt){
            return ;
      }else{
            it++;
            search5(it,eIt,sum);
            it--;
            __int64 p1=(*it);
            bool insertOK=true;
            for(int i=0;i<set5.size();i++){
                  if(cons[p1].find(set5[i])==cons[p1].end()){
                        insertOK=false;
                  }
            }
            if(insertOK==true){
                  set5.push_back((*it));
                  it++;
                  search5(it,eIt,sum+p1);
                  it--;
                  set5.pop_back();
            }
      }
}


int main(){
      bool is_prime[PRIME_LIMIT];
      memset(is_prime,true,sizeof(is_prime));
      is_prime[0]=is_prime[1]=false;    

      std::set<__int64> setE;
   
   
      for(int i=2;i*i<PRIME_LIMIT;i+=1+(i%2)){
            if(is_prime[i]==false)continue;
            int start=4;
            int add=2;
         
            if(i%2==1){
                  start=i*i;
                  add=i*2;
            }
            for(int j=start;j<PRIME_LIMIT;j+=add){
                  is_prime[j]=false;
            }
      }
      for(int i=2;i<PRIME_LIMIT;i++){
            if(is_prime[i]==false)continue;
            if(i<SEARCH_LIMIT)cons[i]=setE;    
            primes.push_back(i);
      }
      __int64 a,b;
      int search_size=cons.size();
      for(int i=0;i<search_size;i++){
            __int64 p1=primes[i];
            for(int j=i+1;j<search_size;j++){
                  if(i==j)continue;
                  __int64 p2=primes[j];
                  if(p1+p2>SEARCH_LIMIT)break;
                  if(isConnectOK(p1,p2)&&isConnectOK(p2,p1)){
                        cons[p1].insert(p2);
                        cons[p2].insert(p1);
                  }
            }
      }
      std::map<__int64,std::set<__int64> >::iterator mIt;
      std::set<__int64>::iterator sIt,eIt;
      for(mIt=cons.begin();mIt!=cons.end();mIt++){
            set5.push_back((*mIt).first);
            sIt=(*mIt).second.upper_bound((*mIt).first);
            eIt=(*mIt).second.end();
            search5(sIt,eIt,(*mIt).first);
            set5.pop_back();
      }
      std::cout<<ans<<"\n";
}