完整格式链接：https://blog.imakiseki.cf/2022/03/11/acmoi/lanqiao/chun-zhi-shu/
蓝桥杯 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()))))
