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

Primes with runs 题号:111 难度: 45 中英对照

Considering 4-digit primes containing repeated digits it is clear that they cannot all be the same: 1111 is divisible by 11, 2222 is divisible by 22, and so on. But there are nine 4-digit primes containing three ones:

1117, 1151, 1171, 1181, 1511, 1811, 2111, 4111, 8111

We shall say that M(n, d) represents the maximum number of repeated digits for an n-digit prime where d is the repeated digit, N(n, d) represents the number of such primes, and S(n, d) represents the sum of these primes.

So M(4, 1) = 3 is the maximum number of repeated digits for a 4-digit prime where one is the repeated digit, there are N(4, 1) = 9 such primes, and the sum of these primes is S(4, 1) = 22275. It turns out that for d = 0, it is only possible to have M(4, 0) = 2 repeated digits, but there are N(4, 0) = 13 such cases.

In the same way we obtain the following results for 4-digit primes.

Digit, d M(4, d) N(4, d) S(4, d)
0 2 13 67061
1 3 9 22275
2 3 1 2221
3 3 12 46214
4 3 2 8888
5 3 1 5557
6 3 1 6661
7 3 9 57863
8 3 1 8887
9 3 7 48073

Solution

显然需要一个循环枚举d,从0到9. 对每个d: 1. 生成一个10位数,每一位都是d,记这个数为x。 2. 检验x是不是素数,如果是,则将它记入答案,并退出。 3. 枚举x的每一位,将该位置上的数字替换为其他数字,检验替换后的x是不是素数,如果是,则将该步骤得到的所有素数记入答案,退出。 4. 枚举x的每两位,将位置上的两个数字替换为其他数字,并检验,…… 5. 3位、4位下去。 注意到程序运行时发现当且仅当d=0时会要求替换3位,其他时候只会替换至多2位即可找到素数。因而不用替换4位。

Code


public final class p111 {
    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 public String run(){
    	int dig[]=new int[10];
    	Long ans=0L;
    	for(int d=0;d<=9;d++){
    		boolean flag=false;
    		for(int i=0;i<10;i++) dig[i]=d;
    		if(dig[0]==0)dig[0]=1;
    		if(check(get(dig))){
    			flag=true;
    			ans+=get(dig);
    		}
    		if(flag) continue;
    		//替换1位
    		for(int i=0;i<10;i++){
    			for(int x=i==0?1:0;x<10;x++) if(x!=d){
    				dig[i]=x;
    				if(check(get(dig))){
    					flag=true;
    					ans+=get(dig);
    				}
    				dig[i]=d;
    			}
    		}
    		if(flag) continue;
    		//替换2位
    		for(int i=0;i<10;i++)for(int j=i+1;j<10;j++){
    			for(int x=i==0?1:0;x<10;x++)if(x!=d) for(int y=0;y<10;y++)if(y!=d){
    				dig[i]=x;dig[j]=y;
    				if(check(get(dig))){
    					flag=true;
    					ans+=get(dig);
    				}
    				dig[i]=d;dig[j]=d;
    			}
    		}
    		if(flag) continue;
    		//替换3位
    		for(int i=0;i<10;i++)for(int j=i+1;j<10;j++)for(int k=i+1;k<10;k++){
    			for(int x=i==0?1:0;x<10;x++)if(x!=d)for(int y=0;y<10;y++)if(y!=d) for(int z=0;z<10;z++)if(z!=d){
    				dig[i]=x;dig[j]=y;dig[k]=z;
    				if(check(get(dig))){
    					flag=true;
    					ans+=get(dig);
    				}
    				dig[i]=d;dig[j]=d;dig[k]=d;
    			}
    		}
    		if(flag) continue;
    		System.err.println("需要替换更多位数");
    	}
    	return ans.toString();
    }
    
    static public boolean check(long a){
    	if(a <1000000000L) return false;
    	if(a>=10000000000L) return false;
    	if(a==2) return true;
    	if(a%2==0) return false;
    	for(long i=3;i<=a/i;i+=2){
    		if(a%i==0) return false;
    	}
    	return true;
    }
    
    static public long get(int[] d){
    	long ans=0;
    	for(int i=0;i<d.length;i++){
    		ans*=10;
    		ans+=d[i];
    	}
    	return ans;
    }
    
}
612407567715
175ms