蓝桥杯真题中，有哪些关于纯质数的具体题目？
- 内容介绍
- 文章标签
- 相关推荐
本文共计1018个文字，预计阅读时间需要5分钟。
蓝桥杯2021年中国赛真题《纯质数》的Python解法。题目链接：https://www.lanqiao.cn/prob
完整格式链接：blog.imakiseki.cf/2022/03/11/acmoi/lanqiao/chun-zhi-shu/
蓝桥杯 2021 年国赛真题《纯质数》的 Python 解法。
蓝桥杯 2021 年国赛真题：纯质数。
题目链接：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
判断质数的代码较为简单，在此不作详述，注意设置循环时除数的上限略高于目标数字的算术平方根即可。
完整代码 Pythonfrom 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()))))
Break your stereo days. Whatever they say you will never stop to believe in yourself. Brave invisible world. You know that it's true you can find the new way.
本文共计1018个文字，预计阅读时间需要5分钟。
蓝桥杯2021年中国赛真题《纯质数》的Python解法。题目链接：https://www.lanqiao.cn/prob
完整格式链接：blog.imakiseki.cf/2022/03/11/acmoi/lanqiao/chun-zhi-shu/
蓝桥杯 2021 年国赛真题《纯质数》的 Python 解法。
蓝桥杯 2021 年国赛真题：纯质数。
题目链接：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
判断质数的代码较为简单，在此不作详述，注意设置循环时除数的上限略高于目标数字的算术平方根即可。
完整代码 Pythonfrom 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()))))
Break your stereo days. Whatever they say you will never stop to believe in yourself. Brave invisible world. You know that it's true you can find the new way.