### Prime digit replacements题号：51 难度： 15 中英对照

By replacing the 1st digit of the 2-digit number *3, it turns out that six of the nine possible values: 13, 23, 43, 53, 73, and 83, are all prime.

By replacing the 3rd and 4th digits of 56**3 with the same digit, this 5-digit number is the first example having seven primes among the ten generated numbers, yielding the family: 56003, 56113, 56333, 56443, 56663, 56773, and 56993. Consequently 56003, being the first member of this family, is the smallest prime with this property.

Find the smallest prime which, by replacing part of the number (not necessarily adjacent digits) with the same digit, is part of an eight prime value family.

### Code

import java.util.Arrays;

public class p51 {
public static void main(String[] args) {
long start=System.nanoTime();
long result = run();
long end=System.nanoTime();
System.out.println(result);
System.out.println( (end-start)/1000000 + "ms" );
}
//记录一个数是不是素数
public static  boolean[] listPrimality(int n) {
if (n < 0)
throw new IllegalArgumentException("Negative array size");
boolean[] result = new boolean[n + 1];
if (n >= 2)
result[2] = true;
for (int i = 3; i <= n; i += 2)
result[i] = true;

for (int i = 3, end = (int)Math.sqrt(n); i <= end; i += 2) {
if (result[i]) {
for (int j = i * i; j <= n; j += i << 1)
result[j] = false;
}
}
return result;
}

public static int run() {
boolean[] isPrime = listPrimality(1000000);
for (int i = 0; i < isPrime.length; i++) {
if (!isPrime[i])
continue;

int[] n = toDigits(i);
int count = 0;
for (int j = 0; j < 10; j++) {
if (digits[0] != 0 && isPrime[toNumber(digits)])
count++;
}

if (count == 8) {
for (int j = 0; j < 10; j++) {
if (digits[0] != 0 && isPrime[toNumber(digits)])
}
}
}
}
}

//将数字转成整形数组，方便对每一位进行操作
private static int[] toDigits(int n) {
int[] buf = new int[10];
int i = buf.length;
do {
i--;
buf[i] = n % 10;
n /= 10;
} while (n != 0);
return Arrays.copyOfRange(buf, i, buf.length);
}

//给数字digits加上模板，即替换其中的某些位
int[] result = new int[digits.length];
for (int i = 0; i < digits.length; i++)
result[i] = digits[i] * (~mask >>> i & 1);
return result;
}

int[] result = new int[digits.length];
for (int i = 0; i < digits.length; i++)
result[i] = digits[i] + (mask >>> i & 1);
return result;
}

private static int toNumber(int[] digits) {
int result = 0;
for (int x : digits)
result = result * 10 + x;
return result;
}
}

121313
132ms