蓝桥杯真题：纯质数

蓝桥杯 2021 年国赛真题《纯质数》的 Python 解法。

蓝桥杯 2021 年国赛真题：纯质数。

题目链接：https://www.lanqiao.cn/problems/1561/learning/（需要登录）。

题目大意

输出 1 到 20210605 之间（包括两端）的“纯质数”（指十进制各数位皆为质数的质数，1 不视作质数）。

分析

Python

本题是填空题，原则上无需时间复杂度较低的程序也可被接受。当然，这里将给出非填空题的解法。

Python 在大数据规模的循环上耗时较大，而本题显然绕不开判断质数这一话题——乍看本题给出的数据规模达到了千万级，判断其是否为质数最坏情况下需要千级别的循环，而我们要判断 20210605 个数字是否为质数，这个耗时显然是不可接受的（预测在 C/C++ 下也难以接受）。

因此我们可以考虑能否降低需要判断是否为质数的数字的数量。注意到本题中所提到的“纯质数”不仅要求其本身是质数，还要求十进制各数位也为质数——这下我们可以先借此排除掉一定不是纯质数的数字，继而大大简化运算量。

经过分析，我们得知如果一个数要满足“十进制各数位为质数”这一条件，必须满足各个数位只可取 2、3、5、7 中的一个。粗略来看，我们省下了约五分之三的运算量。而更进一步，对于不小于 10 的数字，个位数若为 2 或 5，则一定是合数，故也可提前去除。

为了更好地实现上面的需求，我们最好是自行生成纯质数的“候选”，而不是生成一个长度为 20210605 的列表再删除不符合条件的。每一个数位有可以选择的数字，而这些选择都是互不干扰的，因此我们可以利用标准库 itertools 里的 product() 生成器生成笛卡尔积，以便于快速生成符合条件的数字。实现这一需求的主要代码如下：

from itertools import product

# （不小于 10 的数字）非个位可取的数字集合、个位可取的数字集合
_a, _b = (2, 3, 5, 7), (3, 7)

# 生成“候选”数字的生成器
def candidate_gen():
    # 1 位数
    for i in _a:
        yield i
    # 2~8 位数
    for i in range(2, 9):
        # star expression，表示生成 (i-1) 个 `_a`，一个 `_b`
        for j in product(*([_a] * (i-1)), _b):
            # `j` 是一个由各个数位组成的元组，需要先将其拼成一个整数
            x = packtup(j)
            # 超出范围，终止生成
            if x > 20210605:
                return
            yield x

判断质数的代码较为简单，在此不作详述，注意设置循环时除数的上限略高于目标数字的算术平方根即可。

完整代码

Python

from itertools import product

_a, _b = (2, 3, 5, 7), (3, 7)

def packtup(t):
  return sum(map(lambda i: t[::-1][i] * 10 ** i, range(len(t))))

def candidate_gen():
  for i in _a:
    yield i
  for i in range(2, 9):
    for j in product(*([_a] * (i-1)), _b):
      x = packtup(j)
      if x > 20210605:
        return
      yield x

def isprime(x):
  if x == 1:
    return False
  if x == 2:
    return True
  if x % 2 == 0:
    return False
  for i in range(3, int(x ** 0.5) + 1):
    if x % i == 0:
      return False
  return True

print(len(list(filter(isprime, candidate_gen()))))