藍橋杯真題：純質數
完整格式鏈接：//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
判斷質數的程式碼較為簡單，在此不作詳述，注意設置循環時除數的上限略高於目標數字的算術平方根即可。
完整程式碼
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()))))
