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

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".

Solution

直接枚举所有在Long范围内的素数$p,q$,利用两重循环枚举出所有在Long范围内的数$x=p^2 q^3$,然后转化为String判断是否包含200,最后枚举所有位将其替换为0-9的数字判断是否为素数即可。 注意判断素数可使用BigInteger的素性测试函数,迭代次数选择8-10次即可。

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) {
						set.add(n);
						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