蓝桥杯真题:纯质数

完整格式链接: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()))))
1 Like

麻烦站长加一个有关算法竞赛的子版块,谢谢 :blush:

1 Like