当前位置:首页 » Project Euler » 详细页

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?

Solution

直接暴力,对1-9生成全排列,对每个排列进行切割,切割时要求后割出来的数字要比前面割出来的数字大(否则会重复)。

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[10];
    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