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

プロジェクトオイラー問い121～130 - (2013/01/22 (火) 12:04:11) のソース

Problem 128 「六角形に配置されたタイルのうち隣接するタイルと差の値が素数となるものはどれか?」 †
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20128


解法
賢い解法を思いつきませんでした。
とりあえず計算中の枠とその外枠と中枠の数字を地道にループで回してみました。
何故か素数３つに囲まれるピースが六角形の外周の始まりか終わりのポイントのみなのでそこだけ計算してみましたが速度出てません。


 #include<stdio.h>
 #include<iostream>
 bool isPrime(__int64 n){
 	for(int i=2;i*i<=n;i+=(i&1)+1){
 		if(n%i==0)return false;
 	}
 	return true;
 }
 
 int main(){
 	__int64 r=1;
 	__int64 n=8,outLoop=20,inLoop;
 	__int64 nextLoopPoint=8;
 	__int64 ans=2,w=0,lastAns;
 	while(ans<2000){
 		int count=0;
 		if(n==nextLoopPoint){
 			r++;
 			outLoop=nextLoopPoint=n+r*6;
 			inLoop=n-(r-1)*6;
 			count+=isPrime(outLoop-n);
 			count+=isPrime(outLoop+1-n);
 			count+=isPrime(n-inLoop);
 			count+=isPrime(outLoop+6*(r+1)-1-n);
 			count+=isPrime(6*r-1);
 			w=0;
 			if(count==3){
 				lastAns=n;
 				ans++;
 				std::cout<<"(a "<<ans<<" "<<lastAns<<")";
 			}
 		}
 		if(n==nextLoopPoint-1){
 			count+=isPrime(outLoop-n);
 			count+=isPrime(outLoop+1-n);
 			count+=isPrime(n-inLoop);
 			count+=isPrime(n-(n-6*r+1));
 			count+=isPrime(n-(inLoop-6*(r-1)+1));	
 			if(count==3){
 				lastAns=n;
 				ans++;
 				std::cout<<"(b"<<ans<<" "<<lastAns<<")";
 			}
 			n++;
 			continue;
 		}
 		if(w%r==0&&w>0){
 			outLoop++;
 		}else if(w>0){
 			inLoop++;
 		}
 		outLoop++;
 		w++;
 		n++;
 	}
 	std::cout<<"\n("<<lastAns<<")\n";
 }