「プロジェクトオイラー問い41～50」の編集履歴（バックアップ）一覧はこちら
「プロジェクトオイラー問い41～50」(2012/12/21 (金) 16:45:46) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
*問い41
n桁Pandigitalであるとは, 1からnまでの数を各桁に1つずつ持つこととする.
#下のリンク先にあるような数学的定義とは異なる
例えば2143は4桁Pandigital数であり, かつ素数である. n桁（この問題の定義では9桁以下）Pandigitalな素数の中で最大の数を答えよ.
解法
９桁や８桁のパンデジタル数の各桁の和は45と36で9の倍数となっておりこれは８桁と９ケタのパンデジタル数は全て素数でないということを示しています、組み合わせ数を考えると驚く話です。
よって7桁までのパンデジタル数を全て全探索して検討すれば良いと分かります。
末尾の数字が２の倍数であってはいけないや大きな数字から試すなど各種ルールを適用すればもっと計算量が下がるかもしれません。
#include<stdio.h>
#include<stdlib.h>
bool spents[10]={true,false,false,false,false,false,false,false,false,false};
int ans=0;
bool isPrime(int n){
if(n<2)return false;
for(int i=2;i*i<=n;i+=(i&1)+1){
if(n%i==0)return false;
}
return true;
}
bool isPandigital(int n,int keta){
for(int i=0;i<keta;i++){
if(n%10>keta)return false;
n/=10;
}
return true;
}
void saiki(int n,int keta){
if(isPrime(n)&&isPandigital(n,keta)==true&&ans<n){
ans=n;
}
if(7<=keta)return;
for(int i=1;i<=7;i++){
if(spents[i]==false){
spents[i]=true;
saiki(n*10+i,keta+1);
spents[i]=false;
}
}
}
int main(){
saiki(0,0);
printf("%d",ans);
}
*問い42
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2042
ファイルから単語を読み取り、それを数字に置き換えた時三角数になるかどうか調べる問題。
解法
単語を一つずつ読み込んで数字を計算するだけです。
実はＣの処理系ではアルファベットが連続していることは保証されてないのでtoHash関数は実はインチキ関数なのですが、ま手元の環境では連続しているし連続してないことが超レアケースなので気にしません。
スクリプトなら物凄く短く記述できる可能性があります。
一気にデータを読んでスプリットして、それを一気に処理して結果を返す関数に入れて条件を満たすものをカウントさせれば一行で記述が済むかも。
#include<stdio.h>
#include<stdlib.h>
#include<set>
int toHash(char *text){
int re=0;
for(int i=0;text[i]!='\0';i++){
re+=text[i]-'A'+1;
}
return re;
}
int main(){
int ans=0,sum=0;
std::set<int> memo;
for(int i=1;i<50;i++){
sum+=i;
memo.insert(sum);
}
FILE *fp;
if ((fp = fopen("euler42Data.txt", "r")) == NULL) {
printf("file open error!!\n");
exit(EXIT_FAILURE); /* (3)エラーの場合は通常、異常終了する */
}
char text[100],c;
while(1){
fscanf(fp,"\"%[^\"]\"",text);
if(fscanf(fp,"%c",&c)==EOF)break;
if(memo.find(toHash(text))!=memo.end())ans++;
}
fclose(fp);
printf("ans=%d",ans);
}
*問い43
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2043
数1406357289は0から9のPandigital数である (0から9が1度ずつ現れるので). この数は部分列が面白い性質を持っている.
d1を1桁目, d2を2桁目の数とし, 以下順にdnを定義する. この記法を用いると次のことが分かる.
d2d3d4=406は2で割り切れる
d3d4d5=063は3で割り切れる
d4d5d6=635は5で割り切れる
d5d6d7=357は7で割り切れる
d6d7d8=572は11で割り切れる
d7d8d9=728は13で割り切れる
d8d9d10=289は17で割り切れる
このような性質をもつ0から9のPandigital数の総和を求めよ.
解法
再帰関数で全部試すだけです。
先頭桁0が許されるかは不明ですが先頭桁0でこの条件を満たす数はないようです。
#include<stdio.h>
#include<iostream>
bool spents[10]={false,false,false,false,false,false,false,false,false,false};
int mask=1000;
int mod[]={2,3,5,7,11,13,17};
__int64 ans=0;
void saiki(int n,int keta,__int64 num){
if(keta>=4){
if(n%mod[keta-4]!=0)return ;
}
if(keta==10){
ans+=num;
}else{
for(int i=0;i<=9;i++){
if(spents[i]==false){
spents[i]=true;
saiki((n*10+i)%mask,keta+1,num*10+i);
spents[i]=false;
}
}
}
}
int main(){
saiki(0,0,0);
std::cout<<"ans="<<ans;
}
*問い44
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2044
二つの五角数の和と差がともに５角数になるとき差の最小値を求めよという問題。
解法
とりあえず小さい方から全組み合わせを検討するコードを書いてみました。
もちろんこんなコードで速度が出るはずもなくＣ++で４秒もかかっています。
どうしたら速度が出るか、ちょっと考えあぐねています。
変数の数が３つになるとけっこう悩むものです。
#include<stdio.h>
#include<math.h>
#include<iostream>
#include<time.h>
bool is5(__int64 m){
__int64 m1=sqrt(1+24*m);
return m1*m1==1+24*m && (1+m1)%6==0;
}
int main(){
__int64 ans=0,n1,n2;
double start=clock();
for(__int64 a=2;;a++){
if(ans!=0&&6*a-4>ans)break;
n1=(a*(3*a-1))/2;
for(__int64 b=a-1;b>0;b--){
n2=(b*(3*b-1))/2;
if(ans!=0&&n1-n2>=ans)break;
if(is5(n1+n2)&&is5(n1-n2)){
ans=n1-n2;
std::cout<<"("<<n1<<" "<<a<<" "<<n2<<" "<<b<<")";
}
}
}
std::cout<<"ans="<<ans<<" time="<<clock()-start;
}
*問い45
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2045
三角数, 五角数, 六角数は以下のように生成される.
三角数 Tn=n(n+1)/2 1, 3, 6, 10, 15, ...
五角数 Pn=n(3n-1)/2 1, 5, 12, 22, 35, ...
六角数 Hn=n(2n-1) 1, 6, 15, 28, 45, ...
T285 = P165 = H143 = 40755であることが分かる.
次の三角数かつ五角数かつ六角数な数を求めよ.
解法
特に賢い解法を思いつかなかったので、三角数、5角数、６角数を求め、ループの中で３つの数のうち一番小さい数になったものだけをインクリメントしていきます。
そうすると答えがあればきちんとそろうわけです。
#include<stdio.h>
#include<iostream>
int main(){
__int64 t=285+1,p=165,h=143,t1,p1,h1;
while(1){
t1=(t*(t+1))/2;
p1=(p*(3*p-1))/2;
h1=(h*(2*h-1));
if(t1==p1&&t1==h1)break;
if(t1<=p1&&t1<=h1)t++;
if(p1<=t1&&p1<=h1)p++;
if(h1<=t1&&h1<=p1)h++;
}
std::cout<<t1;
}
*問い46
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2046
Christian Goldbachは全ての奇合成数は平方数の2倍と素数の和で表せると予想した.
9 = 7 + 2×1^2
15 = 7 + 2×2^2
21 = 3 + 2×3^2
25 = 7 + 2×3^2
27 = 19 + 2×2^2
33 = 31 + 2×1^2
後に, この予想は誤りであることが分かった.
平方数の2倍と素数の和で表せない最小の奇合成数はいくつか?
解法
小さい数から試します。
２乗の方が検討する数が少なくなるので２乗*２を引いて、残りが素数かどうか検討すれば十分です。
数式で解くのが一番賢いでしょうが、それをする能力は私にはないのでプログラムで楽をします。
#include<stdio.h>
#include<time.h>
bool isPrime(int n){
for(int i=2;i*i<=n;i+=(i&1)+1){
if(n%i==0)return false;
}
return true;
}
int main(){
double start=clock();
for(int a=3;;a+=2){
if(isPrime(a)==true)continue;
bool ok=false;
for(int b=1;b*b*2+2<=a;b++){
if(isPrime(a-b*b*2)==true){
ok=true;
break;
}
}
if(ok==false){
printf("ans=%d",a);
break;
}
}
printf("time %lf",clock()-start);
}
*問い47
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2047
それぞれ2つの異なる素因数を持つ連続する2つの数が最初に現れるのは:
14 = 2 × 7
15 = 3 × 5
それぞれ3つの異なる素因数を持つ連続する3つの数が最初に現れるのは:
644 = 2^2 × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19
最初に現れるそれぞれ4つの異なる素因数を持つ連続する4つの数を求めよ. その最初の数はいくつか?
解法
異なる４数がそんなに大きくない数だと想定し１００万以下で探索してみました。
異なる４数のうち３数が最小の２，３、5だとすると30で残りの一つは４万当たりまでの素数と想定すれば１００万までの４種の異なる素因数からなる数を網羅できます。
最初にこれを再帰関数で求めて後は４つ連続する部分を線形的に探すだけです。
#include<stdio.h>
#include<vector>
#include<time.h>
#include<algorithm>
const int up=40000;
std::vector<int> sosuu;
bool so[up+1];
const int limit=1000*1000;
bool is4[limit+1];
void setSo(){
int i2;//素数を求める処理
memset(so,true,sizeof(so));
so[0]=so[1]=false;
for(int i=4;i<=up;i+=2)so[i]=false;
sosuu.push_back(2);
for(int i=3;i<=up;i+=2){
if(so[i]==false)continue;
sosuu.push_back(i);
i2=i*2;
for(int j=i*3;j<=up;j+=i2){
so[j]=false;
}
}
}
void saiki(__int64 num,int count,int p){
if(num>limit)return;
if(count==4)is4[(int)num]=true;//４種の異なる素因数の組の積を求めてセットする関数
for(int i=p;i<sosuu.size()&&sosuu[i]*num<limit;i++){
saiki(num*sosuu[i],count==0?1:count+(p!=i),i);
if(count==4)break;
}
}
int main(){
double start=clock();
setSo();
memset(is4,false,sizeof(is4));
saiki(1,0,0);
int count=0;
for(int i=2;i<limit;i++){
if(is4[i]==true){
count++;
if(count==4){
printf("ans=%d time=%lf",i-3,clock()-start);
break;
}
}else{
count=0;
}
}
}
*問い48
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2048
次の式は, 1^1 + 2^2 + 3^3 + ... + 10^10 = 10405071317 である.
では, 1^1 + 2^2 + 3^3 + ... + 1000^1000 の最後の10桁を求めよ.
解法
計算回数５０万回なので定義通り計算するだけでも十分間に合います。
大きい数を扱える整数型があれば計算量を減らせますが残念なことにＣ++標準の型では１９桁程度までしか扱えません。
１０ケタ*１０ケタが桁あふれするためにＣ++ではライブラリか特殊な処理が必要となります。
めんどくさいのでそのまま計算しました。
#include<stdio.h>
#include<iostream>
int main(){
__int64 mod=1,sum=0,num;
for(int i=0;i<10;i++)mod*=10;
for(int i=1;i<=1000;i++){
num=i;
for(int j=1;j<i;j++){
num=(num*i)%mod;
}
sum=(sum+num)%mod;
}
std::cout<<sum;
}
*問い49
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2049
項差3330の等差数列1487, 4817, 8147は次の2つの変わった性質を持つ.
(i)3つの項はそれぞれ素数である.
(ii)各項は他の項の置換で表される.
1, 2, 3桁の素数にはこのような性質を持った数列は存在しないが, 4桁の増加列にはもう1つ存在する.
それではこの数列の3つの項を連結した12桁の数を求めよ
解法
探索範囲が狭いのでそのまま全部検討しました。
素数にかかわる問題なので簡単にショートカットする方法はないと思うのですが等差を3330決め打ちで計算してる方がいました。
何か問題の中に規則性でもあるのかも？
#include<stdio.h>
#include<time.h>
bool isPrime(int n){
for(int i=2;i*i<=n;i+=(i&1)+1){
if(n%i==0)return false;
}
return true;
}
bool check(int n1,int n2){
int count[10]={0};
while(n1!=0){
count[n1%10]++;
n1/=10;
}
while(n2!=0){
count[n2%10]--;
if(count[n2%10]<0)return false;
n2/=10;
}
return true;
}
int main(){
double start=clock();
for(int a=1000;a<=9999;a++){
if(isPrime(a)==false)continue;
for(int b=1;a+2*b<=9999;b++){
if(isPrime(a+b)&&isPrime(a+b+b)&&check(a,a+b)&&check(a,a+b+b)){
printf("(%d%d%d)",a,a+b,a+b+b);
}
}
}
printf("\ntime=%lf",clock()-start);
}
*問い50
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2050
素数41は6つの連続する素数の和として表せる:
41 = 2 + 3 + 5 + 7 + 11 + 13.
100未満の素数を連続する素数の和で表したときにこれが最長になる.
同様に, 連続する素数の和で1000未満の素数を表したときに最長になるのは953で21項を持つ.
100万未満の素数を連続する素数の和で表したときに最長になるのはどの素数か?
解法
setso()関数でvector型にsosuu
１００万以下の全部の素数の和をボトムアップで足しこみ足し算の長さが更新されかつ素数ならそれで記録更新します。
それだけで十分速度が出ます。
#include<stdio.h>
#include<vector>
#include<algorithm>
const int up=1000000;
std::vector<int> sosuu;
bool so[up+1];
void setSo(){
int i2;
memset(so,true,sizeof(so));
so[0]=so[1]=false;
for(int i=4;i<=up;i+=2)so[i]=false;
sosuu.push_back(2);
for(int i=3;i<=up;i+=2){
if(so[i]==false)continue;
sosuu.push_back(i);
i2=i*2;
for(int j=i*3;j<=up;j+=i2){
so[j]=false;
}
}
}
void calc(){
int sum,count,ansCount=0,ans=0;
for(int i=0;i<sosuu.size();i++){
sum=sosuu[i];
count=1;
for(int j=i+1;j<sosuu.size()&&sum<up;j++){
if(ansCount<count&&so[sum]==true){
ansCount=count;
ans=sum;
}
sum+=sosuu[j];
count++;
}
}
printf("ans=%d",ans);
}
int main(){
setSo();
calc();
}
*問い41
n桁Pandigitalであるとは, 1からnまでの数を各桁に1つずつ持つこととする.
#下のリンク先にあるような数学的定義とは異なる
例えば2143は4桁Pandigital数であり, かつ素数である. n桁（この問題の定義では9桁以下）Pandigitalな素数の中で最大の数を答えよ.
解法
９桁や８桁のパンデジタル数の各桁の和は45と36で9の倍数となっておりこれは８桁と９ケタのパンデジタル数は全て素数でないということを示しています、組み合わせ数を考えると驚く話です。
よって7桁までのパンデジタル数を全て全探索して検討すれば良いと分かります。
末尾の数字が２の倍数であってはいけないや大きな数字から試すなど各種ルールを適用すればもっと計算量が下がるかもしれません。
#include<stdio.h>
#include<stdlib.h>
bool spents[10]={true,false,false,false,false,false,false,false,false,false};
int ans=0;
bool isPrime(int n){
if(n<2)return false;
for(int i=2;i*i<=n;i+=(i&1)+1){
if(n%i==0)return false;
}
return true;
}
bool isPandigital(int n,int keta){
for(int i=0;i<keta;i++){
if(n%10>keta)return false;
n/=10;
}
return true;
}
void saiki(int n,int keta){
if(isPrime(n)&&isPandigital(n,keta)==true&&ans<n){
ans=n;
}
if(7<=keta)return;
for(int i=1;i<=7;i++){
if(spents[i]==false){
spents[i]=true;
saiki(n*10+i,keta+1);
spents[i]=false;
}
}
}
int main(){
saiki(0,0);
printf("%d",ans);
}
*問い42
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2042
ファイルから単語を読み取り、それを数字に置き換えた時三角数になるかどうか調べる問題。
解法
単語を一つずつ読み込んで数字を計算するだけです。
実はＣの処理系ではアルファベットが連続していることは保証されてないのでtoHash関数は実はインチキ関数なのですが、ま手元の環境では連続しているし連続してないことが超レアケースなので気にしません。
スクリプトなら物凄く短く記述できる可能性があります。
一気にデータを読んでスプリットして、それを一気に処理して結果を返す関数に入れて条件を満たすものをカウントさせれば一行で記述が済むかも。
#include<stdio.h>
#include<stdlib.h>
#include<set>
int toHash(char *text){
int re=0;
for(int i=0;text[i]!='\0';i++){
re+=text[i]-'A'+1;
}
return re;
}
int main(){
int ans=0,sum=0;
std::set<int> memo;
for(int i=1;i<50;i++){
sum+=i;
memo.insert(sum);
}
FILE *fp;
if ((fp = fopen("euler42Data.txt", "r")) == NULL) {
printf("file open error!!\n");
exit(EXIT_FAILURE); /* (3)エラーの場合は通常、異常終了する */
}
char text[100],c;
while(1){
fscanf(fp,"\"%[^\"]\"",text);
if(fscanf(fp,"%c",&c)==EOF)break;
if(memo.find(toHash(text))!=memo.end())ans++;
}
fclose(fp);
printf("ans=%d",ans);
}
*問い43
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2043
数1406357289は0から9のPandigital数である (0から9が1度ずつ現れるので). この数は部分列が面白い性質を持っている.
d1を1桁目, d2を2桁目の数とし, 以下順にdnを定義する. この記法を用いると次のことが分かる.
d2d3d4=406は2で割り切れる
d3d4d5=063は3で割り切れる
d4d5d6=635は5で割り切れる
d5d6d7=357は7で割り切れる
d6d7d8=572は11で割り切れる
d7d8d9=728は13で割り切れる
d8d9d10=289は17で割り切れる
このような性質をもつ0から9のPandigital数の総和を求めよ.
解法
再帰関数で全部試すだけです。
先頭桁0が許されるかは不明ですが先頭桁0でこの条件を満たす数はないようです。
#include<stdio.h>
#include<iostream>
bool spents[10]={false,false,false,false,false,false,false,false,false,false};
int mask=1000;
int mod[]={2,3,5,7,11,13,17};
__int64 ans=0;
void saiki(int n,int keta,__int64 num){
if(keta>=4){
if(n%mod[keta-4]!=0)return ;
}
if(keta==10){
ans+=num;
}else{
for(int i=0;i<=9;i++){
if(spents[i]==false){
spents[i]=true;
saiki((n*10+i)%mask,keta+1,num*10+i);
spents[i]=false;
}
}
}
}
int main(){
saiki(0,0,0);
std::cout<<"ans="<<ans;
}
*問い44
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2044
二つの五角数の和と差がともに５角数になるとき差の最小値を求めよという問題。
解法
とりあえず小さい方から全組み合わせを検討するコードを書いてみました。
もちろんこんなコードで速度が出るはずもなくＣ++で４秒もかかっています。
どうしたら速度が出るか、ちょっと考えあぐねています。
変数の数が３つになるとけっこう悩むものです。
#include<stdio.h>
#include<math.h>
#include<iostream>
#include<time.h>
bool is5(__int64 m){
__int64 m1=sqrt(1+24*m);
return m1*m1==1+24*m && (1+m1)%6==0;
}
int main(){
__int64 ans=0,n1,n2;
double start=clock();
for(__int64 a=2;;a++){
if(ans!=0&&6*a-4>ans)break;
n1=(a*(3*a-1))/2;
for(__int64 b=a-1;b>0;b--){
n2=(b*(3*b-1))/2;
if(ans!=0&&n1-n2>=ans)break;
if(is5(n1+n2)&&is5(n1-n2)){
ans=n1-n2;
std::cout<<"("<<n1<<" "<<a<<" "<<n2<<" "<<b<<")";
}
}
}
std::cout<<"ans="<<ans<<" time="<<clock()-start;
}
*問い45
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2045
三角数, 五角数, 六角数は以下のように生成される.
三角数 Tn=n(n+1)/2 1, 3, 6, 10, 15, ...
五角数 Pn=n(3n-1)/2 1, 5, 12, 22, 35, ...
六角数 Hn=n(2n-1) 1, 6, 15, 28, 45, ...
T285 = P165 = H143 = 40755であることが分かる.
次の三角数かつ五角数かつ六角数な数を求めよ.
解法
特に賢い解法を思いつかなかったので、三角数、5角数、６角数を求め、ループの中で３つの数のうち一番小さい数になったものだけをインクリメントしていきます。
そうすると答えがあればきちんとそろうわけです。
#include<stdio.h>
#include<iostream>
int main(){
__int64 t=285+1,p=165,h=143,t1,p1,h1;
while(1){
t1=(t*(t+1))/2;
p1=(p*(3*p-1))/2;
h1=(h*(2*h-1));
if(t1==p1&&t1==h1)break;
if(t1<=p1&&t1<=h1)t++;
if(p1<=t1&&p1<=h1)p++;
if(h1<=t1&&h1<=p1)h++;
}
std::cout<<t1;
}
*問い46
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2046
Christian Goldbachは全ての奇合成数は平方数の2倍と素数の和で表せると予想した.
9 = 7 + 2×1^2
15 = 7 + 2×2^2
21 = 3 + 2×3^2
25 = 7 + 2×3^2
27 = 19 + 2×2^2
33 = 31 + 2×1^2
後に, この予想は誤りであることが分かった.
平方数の2倍と素数の和で表せない最小の奇合成数はいくつか?
解法
小さい数から試します。
２乗の方が検討する数が少なくなるので２乗*２を引いて、残りが素数かどうか検討すれば十分です。
数式で解くのが一番賢いでしょうが、それをする能力は私にはないのでプログラムで楽をします。
#include<stdio.h>
#include<time.h>
bool isPrime(int n){
for(int i=2;i*i<=n;i+=(i&1)+1){
if(n%i==0)return false;
}
return true;
}
int main(){
double start=clock();
for(int a=3;;a+=2){
if(isPrime(a)==true)continue;
bool ok=false;
for(int b=1;b*b*2+2<=a;b++){
if(isPrime(a-b*b*2)==true){
ok=true;
break;
}
}
if(ok==false){
printf("ans=%d",a);
break;
}
}
printf("time %lf",clock()-start);
}
*問い47
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2047
それぞれ2つの異なる素因数を持つ連続する2つの数が最初に現れるのは:
14 = 2 × 7
15 = 3 × 5
それぞれ3つの異なる素因数を持つ連続する3つの数が最初に現れるのは:
644 = 2^2 × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19
最初に現れるそれぞれ4つの異なる素因数を持つ連続する4つの数を求めよ. その最初の数はいくつか?
解法
異なる４数がそんなに大きくない数だと想定し１００万以下で探索してみました。
異なる４数のうち３数が最小の２，３、5だとすると30で残りの一つは４万当たりまでの素数と想定すれば１００万までの４種の異なる素因数からなる数を網羅できます。
最初にこれを再帰関数で求めて後は４つ連続する部分を線形的に探すだけです。
#include<stdio.h>
#include<vector>
#include<time.h>
#include<algorithm>
const int up=40000;
std::vector<int> sosuu;
bool so[up+1];
const int limit=1000*1000;
bool is4[limit+1];
void setSo(){
int i2;//素数を求める処理
memset(so,true,sizeof(so));
so[0]=so[1]=false;
for(int i=4;i<=up;i+=2)so[i]=false;
sosuu.push_back(2);
for(int i=3;i<=up;i+=2){
if(so[i]==false)continue;
sosuu.push_back(i);
i2=i*2;
for(int j=i*3;j<=up;j+=i2){
so[j]=false;
}
}
}
void saiki(__int64 num,int count,int p){
if(num>limit)return;
if(count==4)is4[(int)num]=true;//４種の異なる素因数の組の積を求めてセットする関数
for(int i=p;i<sosuu.size()&&sosuu[i]*num<limit;i++){
saiki(num*sosuu[i],count==0?1:count+(p!=i),i);
if(count==4)break;
}
}
int main(){
double start=clock();
setSo();
memset(is4,false,sizeof(is4));
saiki(1,0,0);
int count=0;
for(int i=2;i<limit;i++){
if(is4[i]==true){
count++;
if(count==4){
printf("ans=%d time=%lf",i-3,clock()-start);
break;
}
}else{
count=0;
}
}
}
*問い48
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2048
次の式は, 1^1 + 2^2 + 3^3 + ... + 10^10 = 10405071317 である.
では, 1^1 + 2^2 + 3^3 + ... + 1000^1000 の最後の10桁を求めよ.
解法
計算回数５０万回なので定義通り計算するだけでも十分間に合います。
大きい数を扱える整数型があれば計算量を減らせますが残念なことにＣ++標準の型では１９桁程度までしか扱えません。
１０ケタ*１０ケタが桁あふれするためにＣ++ではライブラリか特殊な処理が必要となります。
めんどくさいのでそのまま計算しました。
#include<stdio.h>
#include<iostream>
int main(){
__int64 mod=1,sum=0,num;
for(int i=0;i<10;i++)mod*=10;
for(int i=1;i<=1000;i++){
num=i;
for(int j=1;j<i;j++){
num=(num*i)%mod;
}
sum=(sum+num)%mod;
}
std::cout<<sum;
}
*問い49
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2049
項差3330の等差数列1487, 4817, 8147は次の2つの変わった性質を持つ.
(i)3つの項はそれぞれ素数である.
(ii)各項は他の項の置換で表される.
1, 2, 3桁の素数にはこのような性質を持った数列は存在しないが, 4桁の増加列にはもう1つ存在する.
それではこの数列の3つの項を連結した12桁の数を求めよ
解法
探索範囲が狭いのでそのまま全部検討しました。
素数にかかわる問題なので簡単にショートカットする方法はないと思うのですが等差を3330決め打ちで計算してる方がいました。
何か問題の中に規則性でもあるのかも？
#include<stdio.h>
#include<time.h>
bool isPrime(int n){
for(int i=2;i*i<=n;i+=(i&1)+1){
if(n%i==0)return false;
}
return true;
}
bool check(int n1,int n2){
int count[10]={0};
while(n1!=0){
count[n1%10]++;
n1/=10;
}
while(n2!=0){
count[n2%10]--;
if(count[n2%10]<0)return false;
n2/=10;
}
return true;
}
int main(){
double start=clock();
for(int a=1000;a<=9999;a++){
if(isPrime(a)==false)continue;
for(int b=1;a+2*b<=9999;b++){
if(isPrime(a+b)&&isPrime(a+b+b)&&check(a,a+b)&&check(a,a+b+b)){
printf("(%d%d%d)",a,a+b,a+b+b);
}
}
}
printf("\ntime=%lf",clock()-start);
}
*問い50
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2050
素数41は6つの連続する素数の和として表せる:
41 = 2 + 3 + 5 + 7 + 11 + 13.
100未満の素数を連続する素数の和で表したときにこれが最長になる.
同様に, 連続する素数の和で1000未満の素数を表したときに最長になるのは953で21項を持つ.
100万未満の素数を連続する素数の和で表したときに最長になるのはどの素数か?
解法
setso()関数でvector型にsosuu
１００万以下の全部の素数の和をボトムアップで足しこみ足し算の長さが更新されかつ素数ならそれで記録更新します。
それだけで十分速度が出ます。
#include<stdio.h>
#include<vector>
#include<algorithm>
const int up=1000000;
std::vector<int> sosuu;
bool so[up+1];
void setSo(){
int i2;
memset(so,true,sizeof(so));
so[0]=so[1]=false;
for(int i=4;i<=up;i+=2)so[i]=false;
sosuu.push_back(2);
for(int i=3;i<=up;i+=2){
if(so[i]==false)continue;
sosuu.push_back(i);
i2=i*2;
for(int j=i*3;j<=up;j+=i2){
so[j]=false;
}
}
}
void calc(){
int sum,count,ansCount=0,ans=0;
for(int i=0;i<sosuu.size();i++){
sum=sosuu[i];
count=1;
for(int j=i+1;j<sosuu.size()&&sum<up;j++){
if(ansCount<count&&so[sum]==true){
ansCount=count;
ans=sum;
}
sum+=sosuu[j];
count++;
}
}
printf("ans=%d",ans);
}
int main(){
setSo();
calc();
}
