「プロジェクトオイラー問６０」の編集履歴（バックアップ）一覧に戻る

プロジェクトオイラー問６０ - (2014/02/21 (金) 15:33:31) のソース

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2060

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

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



解法
素数の上限を定めて、素数を点結合可能な２つの点を線で結んでグラフとみて範囲内を全て検証します。
後はグラフの中から五芒星になっているところを見つければアセプトです。
解が見つかれば、解より大きな素数が答えにはいることはありませんから、その近辺を上限にして再度コードを実行すれば答えとなります。


 #include<stdio.h>
 #include<stdlib.h>
 #include<vector>
 #include<string.h>
 #include<set>
 #include<map> 
 #include<iostream>
 
 const int MAX=60000;
 const int SEARCH_MAX=27000;
 std::vector<__int64> primes;
 std::map<int,std::set<int> > cons;
 bool is_primes[MAX];
 
 void prime_list(){
 	memset(is_primes,true,sizeof(is_primes));
 	is_primes[0]=is_primes[1]=false;
 	for(int i=2;i*i<MAX;i++){
 		if(is_primes[i]==false)continue;
 		for(int j=i+i;j<MAX;j+=i){
 			is_primes[j]=false;
 		}
 	}
 	for(int i=2;i<MAX;i++){
 		if(is_primes[i]==true){
 			primes.push_back(i);
 		}
 	}
 }
  
 bool is_prime(__int64 Num){
 	for(int i=0;i<primes.size();i++){
  		__int64 p=primes[i];
 		if(p*p>Num)break;
 		if(Num%p==0)return false;
 	}
 	return true;
 }
 bool con_is_prime(__int64 A,__int64 B){
 	char str[100];
 	__int64 C1,C2;
 	sprintf(str,"%I64lld%I64lld",A,B);
 	sscanf(str,"%I64lld",&C1);
 	if(is_prime(C1)==false)return false;
 	sprintf(str,"%I64lld%I64lld",B,A);
 	sscanf(str,"%I64lld",&C2);
 	return is_prime(C2);
 }
  
 void saiki(int num,std::vector<int>& vec){
 	if(vec.size()==5){
 		int sum=0;
 		for(int i=0;i<vec.size();i++){
 			sum+=vec[i];
 			printf("%d ",vec[i]);
 		}
 		printf("ans=%d \n",sum);
 	}else{
 		std::set<int>::iterator it;
  		for(it=cons[num].upper_bound(num);it!=cons[num].end();it++){
 			bool is_nextOK=true;
 			int nextNum=(*it);
 			for(int i=0;i<vec.size();i++){
 				if(cons[nextNum].find(vec[i])==cons[nextNum].end())is_nextOK=false;
  			}
 			if(is_nextOK){
 				vec.push_back(nextNum);
 				saiki(nextNum,vec);
 				vec.pop_back();
 			}
 		}
 	}
 }
 
 int main(){
 	prime_list();
 	for(int i=0;i<primes.size();i++){
 		__int64 p1 = primes[i];
 		if(p1>SEARCH_MAX)break;
 		for(int j=i+1;j<primes.size();j++){
 			__int64 p2=primes[j];
 			if(p1+p2>SEARCH_MAX)break;
 			if(con_is_prime(p1,p2)){
 				cons[p1].insert(p2);
 				cons[p2].insert(p1);
 			}
 		}
 	}
 	printf("check point 1\n");
 	std::map<int,std::set<int> >::iterator mIt;
 	std::vector<int> vec;
  	for(mIt=cons.begin();mIt!=cons.end();mIt++){
 		vec.push_back((*mIt).first);
 		saiki(vec[0],vec);
 		vec.pop_back();
 	}	
 }