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

プロジェクトオイラー問い41～50 - (2012/12/21 (金) 03:37:19) の編集履歴(バックアップ)

---

問い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);
}