### Pandigital prime sets题号：118 难度： 45 中英对照

Using all of the digits 1 through 9 and concatenating them freely to form decimal integers, different sets can be formed. Interestingly with the set {2,5,47,89,631}, all of the elements belonging to it are prime.

How many distinct sets containing each of the digits one through nine exactly once contain only prime elements?

### Code


public final class p118 {
public static void main(String[] args) {
long start=System.nanoTime();
String result = run();
long end=System.nanoTime();
System.out.println(result);
System.out.println( (end-start)/1000000 + "ms" );
}

static int dig[]={1,2,3,4,5,6,7,8,9};
static boolean vis[]=new boolean;
static int ans=0;

static public long get(int s,int t){
long res=0;
for(int i=s;i<t;i++){
res*=10;
res+=dig[i];
}
return res;
}

static public void solve(int start,long pre){
if(start>=9){
ans++;
}else{
//切割
for(int i=start+1;i<=9;i++){
long num=get(start,i);
if(num>pre && isPrime(num))
solve(i,num);
}
}
}
static public void dfs(int x){
if(x>=9){
//已经排列好了
solve(0,0L);
}else{
for(int i=1;i<=9;i++){
if(vis[i]) continue;
vis[i]=true;
dig[x]=i;
dfs(x+1);
vis[i]=false;
}
}
}

static public String run(){
dfs(0);
return Integer.toString(ans);
}

static public boolean isPrime(long n){
if(n<2) return false;
if(n==2) return true;
if((n&1)==0) return false;
for(long i=3;i<=n/i;i++){
if(n%i==0) return false;
}
return true;
}
}

44680
20413ms