「プロジェクトオイラー問い121~130」の編集履歴(バックアップ)一覧はこちら
追加された行は緑色になります。
削除された行は赤色になります。
#include<stdio.h>
Problem 128 「六角形に配置されたタイルのうち隣接するタイルと差の値が素数となるものはどれか?」 †
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20128
解法
賢い解法を思いつきませんでした。
とりあえず計算中の枠とその外枠と中枠の数字を地道にループで回してみました。
何故か素数3つに囲まれるピースが六角形の外周の始まりか終わりのポイントのみなのでそこだけ計算してみましたが速度出てません。
#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";
}
Problem 128 「六角形に配置されたタイルのうち隣接するタイルと差の値が素数となるものはどれか?」 †
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20128
解法
賢い解法を思いつきませんでした。
とりあえず計算中の枠とその外枠と中枠の数字を地道にループで回してみました。
何故か素数3つに囲まれるピースが六角形の外周の始まりか終わりのポイントのみなのでそこだけ計算してみましたが速度出てません。
#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";
}