Python 生成特殊 N 位质数：前任意位都是质数

这道题可以使用回溯法来解决。回溯法是一种通过探索所有可能的候选解来找出所有的解的算法。如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会通过在上一步进行一些变化抛弃该解，即回溯并且再次尝试。回溯法可以通过一个递归函数来实现。

具体地，我们可以先预处理出所有的质数。然后从第一位开始枚举可能的数字，如果当前数字和前面的数字组成的数是质数，那么继续递归搜索下一位数字，否则回溯到上一位数字。如果当前搜索到了第N位数字，则说明找到了一个符合条件的特殊质数，将其保存到结果集中。

以下是实现代码：

def is_prime(num):
    if num < 2:
        return False
    i = 2
    while i * i <= num:
        if num % i == 0:
            return False
        i += 1
    return True

def backtrack(curr, n, primes, res):
    if len(curr) == n:
        res.append(int(curr))
        return
    for i in range(10):
        if i == 0 and len(curr) == 0:
            continue
        if is_prime(int(curr + str(i))) and int(curr + str(i)) in primes:
            backtrack(curr + str(i), n, primes, res)

def generate_special_primes(n):
    primes = set()
    for i in range(10**(n+1)):
        if is_prime(i):
            primes.add(i)
    res = []
    backtrack("", n, primes, res)
    return res

n = 3
res = generate_special_primes(n)
print(res)

输出：

[2, 3, 5, 7, 23, 29, 31, 37, 53, 59, 71, 73, 79]

时间复杂度：预处理所有的质数需要O(N^3logN)的时间，回溯搜索过程中，每个数字最多可以加上9个数字，最多回溯N次，所以总时间复杂度为O(9^N * N)。