*問い41 n桁Pandigitalであるとは, 1からnまでの数を各桁に1つずつ持つこととする. #下のリンク先にあるような数学的定義とは異なる 例えば2143は4桁Pandigital数であり, かつ素数である. n桁(この問題の定義では9桁以下)Pandigitalな素数の中で最大の数を答えよ. 解法 9桁や8桁のパンデジタル数の和は45と36で9の倍数となっておりこれは8桁と9ケタのパンデジタル数は全て素数でないということを示しています、組み合わせ数を考えると驚く話です。 よって7桁までのパンデジタル数を全て全探索して検討すれば良いと分かります。 末尾の数字が2の倍数であってはいけない等各種ルールを適用すればもっと計算量が下がるかもしれません。 #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); }