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の範囲を超えない値で助かりました。