プロジェクトオイラー問118 - sinapusu2002 @ ウィキ

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20118
Problem 118 「パンデジタル素数集合」 †

解法
再帰Aで127なら127,172,217,271,712,721と127を並べ替えたもののうち素数であるものを集計し。
集計した結果を使って再帰Bで全探索。
計算時間2.87秒。

結構手が込んでる割に遅い。
複雑でダサいコードになった。
シンプルでわかりやすいのがかっこいいと思う。

#include <iostream>
#include<stdio.h>
#include<map>
using namespace std;

std::map<int,int> count;
bool is_prime(int n){
	if(n==2)return true;
	if((n<2) || (n%2==0))return false;
	for(int i=3;i*i<=n;i+=2){
		if(n%i==0)return false;
	}
	return true;
} 


void saikiA(int num,int bit,int keta){
	if(is_prime(num)){
		count[bit]++;
	}
	if(keta==8)return;
	for(int i=1;i<=9;i++){
		int b=(1<<(i-1));
		if((bit&b)>0)continue;
 		saikiA(num*10+i,bit+b,keta+1);
	}
}
 
int saikiB(int bit,int nowBit,int keta,int d,int mult){
	int re=0;
	if(mult==0)return 0;
	if(keta==9){
		return mult*count[nowBit];
	}
	
	for(int i=1;i<=9;i++){
		int b=1<<(i-1);
		if((bit&b)==0){
			re+= saikiB(bit+b,b,keta+1,i+1,mult*count[nowBit]);
			break;
 		}
	}
	for(int i=d;i<=9;i++){
		int b=1<<(i-1);
		if((bit&b)==0){
			re+=saikiB(bit+b,nowBit+b,keta+1,i+1,mult);
		}
	}
	return re;
}

 
int main() {
	// your code goes here
	for(int i=0;i<512;i++)count[i]=0;
	saikiA(0,0,0);
 	printf("%d",saikiB(1,1,1,1,1));
	return 0;
}