プロジェクトオイラー問60 - sinapusu2002 @ ウィキ

Problem 60 「素数ペア集合」 †

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

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

解法
コードを実行するたびに上限を少しずつ増やしながら全探索するしか思いつきません。

#include<stdio.h>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
std::map<int,std::set<int> > memo;
const int LIMIT=25000;
bool isPrime(__int64 n){
	for(__int64 i=2;i*i<=n;i+=1+(i&1)){
		if(n%i==0)return false;
	}
	return true;
}

int f2(std::set<int>& s1,int no){
	std::set<int>::iterator it;
	for(it=s1.begin();it!=s1.end();it++){
		if((*it)==no)continue;
		if(memo[no].find((*it))==memo[no].end())return -1;
	}
	
	if(s1.size()==5){
		int res=0;
		for(it=s1.begin();it!=s1.end();it++){
			res+=(*it);
		}
 		return res;
	}
	
	int res=1000*1000;
	
	for(it=memo[no].begin();it!=memo[no].end();it++){	
		int no2=(*it);
		if(s1.find(no2)!=s1.end())continue;
		s1.insert(no2);
		int a=f2(s1,no2);
		s1.erase(no2);
		if(a!=-1)res=std::min(res,a);
	}
	return res;
} 

int main(){
	
	std::vector<int> vec;
	for(int i=2;i<=LIMIT;i+=1+(i&1)){
		if(isPrime(i)==true)vec.push_back(i);
	}
	for(int i=0;i<vec.size();i++){
		__int64 p1=vec[i];
		for(int j=i+1;j<vec.size();j++){
			__int64 p2=vec[j];
			__int64 d=1;
			while(p2>d){
				d*=10;
			}
			__int64 p3=p1*d+p2;
			if(isPrime(p3)==true){
 				d=1;
				while(p1>d){
					d*=10;	
				}
				p3=p2*d+p1;
				if(isPrime(p3)==true){
					memo[p2].insert(p1);
					memo[p1].insert(p2);
				}
			}
		}
	}
	std::set<int> s1;
	int ans=1000*1000;
	for(int i=0;i<vec.size();i++){
		s1.insert(vec[i]);
		int a=f2(s1,vec[i]);
		s1.erase(vec[i]);
		if(a!=-1)ans=std::min(ans,a);
	}
	printf("%d\n",ans);
}