### Find the 200th prime-proof sqube containing the contiguous sub-string "200"题号：200 难度： 65 中英对照

We shall define a sqube to be a number of the form, p2q3, where p and q are distinct primes.
For example, 200 = 5223 or 120072949 = 232613.

The first five squbes are 72, 108, 200, 392, and 500.

Interestingly, 200 is also the first number for which you cannot change any single digit to make a prime; we shall call such numbers, prime-proof. The next prime-proof sqube which contains the contiguous sub-string "200" is 1992008.

Find the 200th prime-proof sqube containing the contiguous sub-string "200".

### Code

import java.math.BigInteger;
import java.util.TreeSet;

public final class p200 {
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() {
TreeSet<Long> set = new TreeSet<Long>();
int count = 0;
long max = Long.MAX_VALUE;
for (long v = 1;; v++) {
if (!prime(v))
continue;
long x = v * v * v;
if (x > max)
break;
for (long w = 1;; w++) {
if (v == w)
continue;
if (!prime(w))
continue;
long n = x * w * w;
if (n > max)
break;
String s = n + "";
if (s.contains("200")) {
boolean succ = true;
char ch[] = s.toCharArray();
out: for (int i = 0; i < ch.length; i++) {
char c = ch[i];
for (ch[i] = i == 0 ? '1' : '0'; ch[i] <= '9'; ch[i]++) {
if (prime(new BigInteger(new String(ch)))) {
succ = false;
break out;
}
}
ch[i] = c;
}
if (succ) {
if (set.size() > 200) {
while (set.size() > 200) {
set.pollLast();
}
max = Math.min(max, set.last());
}
}
}
}
}
return set.last()+"";
}
static boolean prime(long n) {
return prime(BigInteger.valueOf(n));
}

static boolean prime(BigInteger n) {
return n.isProbablePrime(8);
}

}
229161792008
3013ms