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

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