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

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2051
Problem 51 「素数の桁置換」 †
,*3の第1桁を置き換えることで, 13, 23, 43, 53, 73, 83という6つの素数が得られる.
56**3の第3桁と第4桁を同じ数で置き換えることを考えよう. この5桁の数は7つの素数をもつ最初の例である: 56003, 56113, 56333, 56443, 56663, 56773, 56993. よって, この族の最初の数である56003は, このような性質を持つ最小の素数である.

桁を同じ数で置き換えることで8つの素数が得られる最小の素数を求めよ. (注:連続した桁でなくても良い)

賢い方法を思いつかなかったので上限を決めて全探索。
最新のパソコンでも数秒かかるとか恥ずかしいな。

#include<stdio.h>
#include<stdlib.h>
#include<string>
#include<sstream>
#include<map>


const int LIMIT=1000000;
bool not_prime[LIMIT]={1,1,0};

std::map<std::string,int> counter,minMemo;

void saiki(int num,int p,std::string str,char c){
	if(p==str.size()){
		if(str.find("*")!=std::string::npos){
			counter[str]++;
			if(minMemo.find(str)==minMemo.end())minMemo[str]=num;
		}
	}else{
		saiki(num,p+1,str,c);
		if(str[p]==c){
			str[p]='*';
			saiki(num,p+1,str,c);
		}
	}
} 

 
int main(){
	
	for(int i=2;i*i<=LIMIT;i+=1+(i&1)){
		if(not_prime[i]==true)continue;
		int start=4,add=2;
 		
		if(i%2==1){
			start=i*3;
			add=i*2;
		}
		for(int j=start;j<LIMIT;j+=add){
			not_prime[j]=true;
		}
	}
	std::stringstream ss;
	std::string str,str2;
	
	std::map<std::string,int>::iterator it;
 	for(int i=10;i<LIMIT;i++){
		if(not_prime[i]==true)continue;
		ss.str("");
		ss.clear(std::stringstream::goodbit);
		ss<<i;
 		ss>>str;
		for(char c='0';c<='9';c++){
			saiki(i,0,str,c);
		}
 	}
	int ans=-1;
	for(it=counter.begin();it!=counter.end();it++){
		if((*it).second==8){
 			int m=minMemo[(*it).first];
			if(ans==-1||m<ans)ans=m;
		}
	}
	printf("counterSize=%d ans=%d",counter.size(),ans);
}