Project Euler 200

题目

Find the $200\text{th}$ prime-proof sqube containing the contiguous sub-string “$200$”

We shall define a sqube to be a number of the form, $p^2q^3$, where $p$ and $q$ are distinct primes.

For example, $200 = 5^2\times 2^3$ or $120072949 = 23^2\times 61^3$.
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 $200\text{th}$ prime-proof sqube containing the contiguous sub-string “$200$”.

解决方案

令$Q=200$。由于本题所需要的质数上限比较难判定，所以使用的上限为$M=200000$。

从小到大枚举所有满足形如$p^2q^3$的数。本题通过之间产生的质数直接从小到大枚举。为保证每次枚举的值最小，使用了优先队列。

枚举时，为了避免枚举到$p=q$的情况，因此从一开始到整个的枚举过程，都需要保证$p< q$或者是$p>q$。此外，为了保证不重不漏，以$p< q$的情形为例：当$p=2$时，可以往右枚举$q$，也可以往下枚举$p$，但是，一旦$p$被枚举过，就不能再枚举$q$了。（枚举示意图如下）因为此时枚举$q$会导致大量的重复枚举，使程序运行很慢。

基于$p^2q^3$变一位是否为质数，这个直接调用库的算法判定。

代码

from tools import is_prime, get_prime
from queue import PriorityQueue

Q = 200
M = 200000


def judge(n: int):
    s = str(n)
    l = len(s)
    for i in range(l):
        d = int(s[i])
        for j in range(10):
            if i + j == 0 or d == j:
                continue
            x = int(s[:i] + str(j) + s[i + 1:])
            if is_prime(x):
                return False
    return True


q = PriorityQueue()
pr = get_prime(M)
q.put((pr[0] ** 2 * pr[1] ** 3, 0, 1))
q.put((pr[1] ** 2 * pr[0] ** 3, 1, 0))
cnt = 0
while True:
    w, x, y = q.get()
    if "200" in str(w) and judge(w):
        cnt += 1
        if cnt == Q:
            ans = w
            break
    if x + 1 != y and not (x > y and y != 0):
        q.put((pr[x + 1] ** 2 * pr[y] ** 3, x + 1, y))
    if x != y + 1 and not (x < y and x != 0):
        q.put((pr[x] ** 2 * pr[y + 1] ** 3, x, y + 1))

print(ans)