Project Euler 41
n桁の数がPandigitalであるとは, 1からnまでの数を各桁に1つずつもつことである. 例えば2143は4桁のPandigital数であり, かつ素数である. n桁のPandigitalな素数の中で最大の数を答えよ.
Mathematica
ans = {}; For[i = 2, i < 10, i++, A = Map[FromDigits[#] &, Permutations[Range[i]]]; ans = Append[ans, Max[Select[A, PrimeQ]]]; ] Max[ans]
実は Pandigital な素数がまずかなり少ない。
めんどくさいので、Permutationsの関数でpandigitalな数を全通り素数かどうか検証しています。
多言語でも、permutation関数を作成できればほぼ終わりかと思います。
C/C++
/* n桁の数がPandigitalであるとは, 1からnまでの数を各桁に1つずつもつことである. 例えば2143は4桁のPandigital数であり, かつ素数である. n桁のPandigitalな素数の中で最大の数を答えよ. */ #include <iostream> #include <deque> using namespace std; const int NUMSIZE = 10; bool num[NUMSIZE]; deque<bool> p; /* maxまでの素数を計算する。 あらかじめ deque<bool> p; をグローバルで宣言しておいてね */ void calc_prime(const int max){ for(int i=0 ; i<max+1 ; i++){ p.push_back(true); } p[0] = false; p[1] = false; double myEnd = sqrt(double(max)); for(int i=2 ; i < myEnd ; i++){ for(int j=2 ; i*j<=max ; j++){ p[i*j] = false; } } } // nが素数かどうか bool is_prime(int n){ return p[n]; } // num初期化 void numInit(){ for(int i=0 ; i<NUMSIZE ; i++){ num[i] = true; } } // nの階乗を返す int factorial(int n){ if(n==0 || n==1) return 1; int k=1; for(int i=2 ; i<=n ; i++){ k*=i; } return k; } // num中でn番目のtrueの位置を返す int trueAt(int n){ int pos=0, tgt=0; while(1){ if(num[pos]){ if(n==tgt) break; tgt++; } if(n==tgt-1) break; pos++; } return pos; } // dig桁の、n番目の順列の数を返す。(intの範囲的に9桁が限界) int PermutationAt(int dig, int n){ numInit(); int ans=0; for(int j=dig-1 ; j>=0 ; j--){ ans *=10; int k = (int)(((n-1)%factorial(j+1))/factorial(j)); int p = trueAt(k); //cout << p; ans +=p+1; num[p] = false; } return ans; //return 0; } int main(){ calc_prime(10000000); cout << "Primes are calculated" << endl; int s; for(int dig=1 ; dig<=7 ; dig++){ for(int j=factorial(dig); j>0 ; j--){ s = PermutationAt(dig, j); if(is_prime(s)){ cout << s << endl; //最初に見つかった素数はdig桁のpandigitalな数の中では最大 break; } } } int end; cin >> end; return 0; }
関数すっげぇ増えちゃった。答えがintの範囲を超えない値で助かりました。