蓝桥杯真题（纯质数）蓝桥杯真题：纯质数

完整格式链接：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 xdef 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 Trueprint(len(list(filter(isprime, candidate_gen()))))