kazm_m の部屋
ProjectEuler 41~
最終更新:
kazm_m
-
view
もうちょっとスマートなプログラムを書きたいところだが・・・
問題41
#include<stdio.h> int sosu(long long n){ int i; for(i=2;i*i<=n;i++){ if(n%i==0)return 0; } return 1; } int keta(long long n){ int re=1; while((n/=10)>=1)re++; return re; } int check(long long n){ int i,a[10],ke; if(sosu(n)==0)return 0; ke=keta(n); for(i=0;i<10;i++)a[i]=0; while(n>=1){ a[n%10]++; n/=10; } for(i=1;i<=ke;i++){ if(a[i]!=1)return 0; } return 1; } int main(){ long long i; for(i=1;;i+=2){ if(check(i)==1){ printf("%lld\n",i); } } return 0; }
問題42
#include<stdio.h> #include<stdlib.h> #include<math.h> int main(){ int Ans=0,now=0,tmp; char ch; FILE*fp; fp=fopen("words.txt","r"); if(fp==NULL)return 0; while(EOF!=fscanf(fp,"%c",&ch)){ if(ch=='"'||ch==','){ if(now==0)continue; tmp=sqrt(now*2); if(tmp*(tmp+1)==now*2)Ans++; now=0; puts(""); }else{ printf("%c",ch); now+=(ch-'A'+1); } } printf("Ans=%d\n",Ans); }
問題43
#include<stdio.h> int sum[15]; int a[10],b[10]; int kaizyo(int n){ if(n<=1)return 1; return n*kaizyo(n-1); } int suti(int a,int c){ return (b[a]*100+b[a+1]*10+b[a+2])%c; } void check(int n){ int i,j,now=n,tmp; for(i=0;i<10;i++){ a[i]=0; b[i]=0; } for(i=9;i>=0;i--){ if(i)tmp=now/kaizyo(i); else tmp=0; now-=tmp*kaizyo(i); for(j=0;tmp>=0;j++){ if(a[j]==0)tmp--; if(tmp==-1){ a[j]=1; b[i]=j; break; } } } if(b[3]%2==0 && (b[2]+b[3]+b[4])%3==0 && b[5]%5==0 && !suti( 4,7)){ if(!suti(5,11) && !suti(6,13) && !suti(7,17)){ for(i=0;i<10;i++)sum[i]+=b[i]; } } } int main(){ int i,j; for(i=0;i<15;i++)sum[i]=0; for(i=0;i<kaizyo(10);i++)check(i); for(i=9;i;i--){ sum[i-1]+=sum[i]/10; sum[i]%=10; } for(i=0;i<10;i++)printf("%d",sum[i]); return 0; }
問題44
/*後で書きなおす*/ #include<stdio.h> #include<math.h> int main(){ int i,j,a,b; float c,d; for(i=1;i<10000;i++){ a=i*(3*i-1)/2; for(j=1;j<i;j++){ b=j*(3*j-1)/2; c=(sqrt(1+24*(a-b))+1)/6; d=(sqrt(1+24*(a+b))+1)/6; if(floor(c)==c && floor(d)==d){ printf("%d %d %d\n",a,b,a-b); return 0; } } } return 0; }
問題45
#include<stdio.h> int main(){ long long i=2,j=2,inow=1,jnow=1; while(1){ if(inow<jnow){ for(;inow<jnow;i++){ inow=i*(2*i-1); } }else if(inow>jnow){ for(;inow>jnow;j++){ jnow=j*(3*j-1)/2; } }else{ printf("%lld\n",inow); inow=i*(2*i-1); i++; } } return 0; }
問題46
#include<stdio.h> int sosu(int n){ int i; for(i=2;i*i<=n;i++){ if(n%i==0)return 0; } return 1; } int main(){ int i,j,flag; for(i=3;i<1e7;i+=2){ if(!sosu(i)){ for(j=1,flag=0;2*j*j<i;j++){ if(sosu(i-2*j*j))flag=1; } if(!flag){ printf("%d\n",i); return 0; } } } return 0; }
問題47
#include<stdio.h> int soinsu(int n){ int i,j,a[20]; //printf("%d: ",n); for(i=0;i<20;i++)a[i]=0; for(i=2;i*i<=n;i++){ if(n%i==0){ n/=i; for(j=0;;j++){ if(a[j]==0){ a[j]=i; break; } if(a[j]==i)break; } i=1; } } for(j=0;;j++){ if(a[j]==0){ a[j]=n; break; } if(a[j]==n)break; } for(i=0;a[i];i++){ // printf("%d ",a[i]); }; //puts(""); return i; } int main(){ int i,j,count=0; for(i=1;;i++){ if(soinsu(i)==4){ count++; }else{ count=0; } if(count>=4){ printf("Ans=%d\n",i-3); return 0; } } return 0; }
問題48
#include<stdio.h> int Ori[15],Ans[15],Tmp[15]; void cul(int a,int b){ int i,j,k; for(i=0;i<=10;i++){ Ori[i]=Ans[i]=Tmp[i]=0; } for(i=0;a>0;i++){ Ori[i]=a%10; a/=10; } for(i=0,Ans[0]=1;i<b;i++){ for(j=0;j<11;j++){ for(k=0;j+k<11;k++){ Tmp[j+k]+=Ori[j]*Ans[k]; Tmp[j+k+1]+=Tmp[j+k]/10; Tmp[j+k]%=10; } } for(j=0;j<11;j++){ Ans[j]=Tmp[j]; Tmp[j]=0; } } } int main(int argc,char*argv[]){ int i,j,*Ans2=calloc(15,sizeof(int)); for(i=1;i<=atoi(argv[1]);i++){ cul(i,i); for(j=0;j<13;j++){ Ans2[j]+=Ans[j]; Ans2[j+1]+=Ans2[j]/10; Ans2[j]%=10; } } for(i=9;i>=0;i--){ printf("%d",Ans2[i]); } return 0; }
問題49
#include<stdio.h> int sosu(int n){ int i; for(i=2;i*i<=n;i++){ if(n%i==0)return 0; } return 1; } int check(int a,int b){ int i,tmp1[10],tmp2[10]; for(i=0;i<10;i++)tmp1[i]=tmp2[i]=0; while(a>0){ tmp1[a%10]++; a/=10; } while(b>0){ tmp2[b%10]++; b/=10; } for(i=0;i<10;i++){ if(tmp1[i]!=tmp2[i])return 0; } return 1; } int main(){ int i,j,k; for(i=1001;i<10000;i++){ if(!sosu(i))continue; for(j=1;i+2*j<10000;j++){ if(sosu(i+j)&&sosu(i+2*j)&&check(i,i+j)&&check(i,i+2*j)){ printf("%d%d%d\n",i,i+j,i+j+j); } } } return 0; }
問題50
#include<stdio.h> #include<stdlib.h> int main(){ long i,j,sum=0,now=0,k=1; int *map=(int*)malloc(1e6*sizeof(int)); long *map2=(long*)calloc(1e6,sizeof(long)); for(i=0;i<1e6;i++)map[i]=1; for(i=4;i<1e6;i+=2)map[i]=0; for(i=3,k=1,map2[0]=2;i<1e6;i+=2){ if(map[i]){ map2[k++]=i; for(j=2;i*j<1e6;j++){ map[i*j]=0; } } } for(i=0;i<1e6;i++){ for(j=i,sum=0;sum<1e6 && j<k;j++){ sum+=map2[j]; if(j-i+1>now && sum<1e6 && map[sum] ){ printf("length=%d val=%d\n",j-i+1,sum); now=j-i+1; } } } return 0; }
問題51
#include<stdio.h> int *a; int beki(int n){ int i,re=1; for(i=0;i<n;i++)re*=2; return re; } int keta(int n){ int re=0; for(;n>=1;n/=10,re++); return re; } int check(int n,int flag){ int i,j,k,tmp,tmp2,count,re=0,flag2,flag3; int hai[10]; char ch[10]; for(i=1;i<beki(keta(n));i++){ count=0; sprintf(ch,"%d",n); tmp=i; flag2=0; flag3=0; for(k=0;k<beki(k);k++){ if(tmp>=beki(keta(n)-k-1)){ tmp-=beki(keta(n)-k-1); if(flag2==0){ tmp2=ch[k]-'0'; flag2=1; }else{ if(tmp2!=ch[k]-'0')flag3=1; } } } if(flag3==1)continue; if(beki(keta(n)-1)==i)continue; for(j=0;j<10;j++){ tmp=i; for(k=0;k<beki(k);k++){ if(tmp>=beki(keta(n)-k-1)){ tmp-=beki(keta(n)-k-1); ch[k]=j+'0'; } } if(a[atoi(ch)]==0 && keta(atoi(ch))==keta(n)){ count++; if(flag)puts(ch); } } if(flag)puts("--------------"); if(re<count)re=count; } return re; } int main(){ int i,j,k=0; a=calloc(1e6,sizeof(int)); for(i=4;i<1e6;i+=2)a[i]=1; for(i=3;i<1e6;i+=2){ if(a[i]==0){ for(j=2;i*j<1e6;j++){ a[i*j]=1; } } } for(i=3;;i+=2){ if(a[i]==0){ if(check(i,0)>=8){ printf("Ans=%d Num=%d\n",i,check(i,1)); return 0; } } } return 0; }
問題52
#include<stdio.h> int a[10]; void check(int n,int*a){ int i; for(i=0;i<10;i++)a[i]=0; while(n>0){ a[n%10]++; n/=10; } return; } int main(){ int i,j,k,b[10],flag; for(i=1;;i++){ check(i,b); flag=1; for(j=1;j<=5;j++){ check(i*j,a); for(k=0;k<10;k++){ if(a[k]!=b[k])flag=0; } } if(flag==1){ printf("%d\n",i); return 0; } } return 0; }
問題53
#include<stdio.h> int make(long a,long b){ long i,re=1; for(i=1;i<=b && re<=1e6;i++){ re*=(a-i+1); re/=i; } if(re>1e6)return 1; return 0; } int main(){ int i,j,k,result=0; for(i=1;i<=100;i++){ for(j=1;2*j<=i;j++){ if(make(i,j)){ result+=(2*(i/2-j+1)); if(i%2==0)result--; break; } } } printf("%d個\n",result); return 0; }
問題59
#include<stdio.h> int main(int argc,char*argv[]){ FILE*fp; int hai[10000]; int i=0,j,k,point,ma,result=0; int key,key1,key2; char ch,ch1,ch2; if(argc<2||!(fp=fopen(argv[1],"r")))return 0; while(EOF!=fscanf(fp,"%d",&hai[i++])){ if(EOF==fscanf(fp,"%c",&ch))break; if(ch!=',')break; }; for(ma=0,key='a';key<='z';key++){ point=0; for(j=0;j<i;j+=3){ if((hai[j]^key)>='a'&&(hai[j]^key)<='z'){ point++; } } if(point>ma){ ma=point; ch=key; } } printf("Key=%c",ch); for(ma=0,key1='a';key1<='z';key1++){ point=0; for(j=1;j<i;j+=3){ if((hai[j]^key1)>='a'&&(hai[j]^key1)<='z'){ point++; } } if(point>ma){ ma=point; ch1=key1; } } printf("%c",ch1); for(ma=0,key2='a';key2<='z';key2++){ point=0; for(j=2;j<i;j+=3){ if((hai[j]^key2)>='a'&&(hai[j]^key2)<='z'){ point++; } } if(point>ma){ ma=point; ch2=key2; } } printf("%c\n",ch2); for(j=0;j<i;j++){ if(j%3==0){ printf("%c",hai[j]^ch); result+=(hai[j]^ch); } if(j%3==1){ printf("%c",hai[j]^ch1); result+=(hai[j]^ch1); } if(j%3==2){ printf("%c",hai[j]^ch2); result+=(hai[j]^ch2); } } printf("\nANS=%d\n",result); return 0; }