从蓝桥杯真题解析纯质数：埃氏筛算法与Python高效实现

1. 从一道蓝桥杯真题说起：什么是“纯质数”？

最近在整理蓝桥杯的历年真题时，又看到了第十二届省赛的这道“纯质数”题目。说实话，第一次看到这个名词，我也愣了一下。质数我们都知道，2， 3， 5， 7... 那“纯质数”又是什么新概念？仔细读题才发现，它的定义其实很直观：一个质数，如果它的每一位数字也都是质数，那么这个质数就被称为纯质数。

举个例子，数字23本身是一个质数，它的个位3是质数，十位2也是质数，所以23就是一个纯质数。再比如19，它本身是质数，但它的个位9不是质数（9能被3整除），所以19就不是纯质数。题目通常要求我们找出在某个范围内（比如1到20210605）所有这样的数，并统计个数。这听起来像是一个结合了数论和编程的经典问题，考察点很明确：一是对质数判断算法的掌握，二是对数字按位处理的能力。

为什么这道题值得拿出来单独讲？因为它完美地体现了算法竞赛中“概念包装”和“基础能力融合”的命题思路。题目本身不发明新的数学定理，而是用一个简单的“纯”字，把质数判断和数字分解这两个基础操作捆绑在一起，制造了一个需要多步思考的关卡。对于初学者来说，直接写一个双重循环暴力判断，很可能因为范围过大而导致超时；而对于有经验的选手，则会立刻意识到需要更高效的质数筛选算法。接下来，我们就从最朴素的思路开始，一步步拆解这个问题，并最终给出一个高效、可靠的Python解决方案。

2. 解题核心思路拆解：两步走策略

面对“纯质数”问题，最直接的思路就是一个一个数去检查。但作为一个合格的解题者，我们不能只满足于“能做出来”，更要追求“做得漂亮、做得高效”。整个解题过程可以清晰地分为两个核心步骤，我称之为“两步走”策略。

2.1 第一步：高效生成质数表

这是整个算法的基石。题目范围动辄上千万（如20210605），如果对每个数都用试除法判断是否为质数，时间复杂度接近O(N√N)，在竞赛的时间限制内几乎是不可接受的。因此，我们必须使用更高效的质数筛选算法。

最经典且实用的算法是埃拉托斯特尼筛法。它的思想非常巧妙：假设我们要找出所有小于等于N的质数。首先列出从2到N的所有整数。然后，从最小的质数2开始，划去列表中所有2的倍数（除了2本身）。接着，找到下一个未被划去的数（此时是3），它一定是质数，再划去所有3的倍数。重复这个过程，直到处理完所有小于等于√N的数。剩下的未被划去的数就都是质数了。

为什么只需要检查到√N？因为如果N是一个合数，那么它必定有一个不大于√N的质因子。这个结论大大减少了我们的工作量。使用埃氏筛，我们可以将时间复杂度降低到O(N log log N)，对于千万级别的数据量完全够用。

2.2 第二步：逐位检查数字的“纯度”

当我们通过筛选法得到一个布尔数组is_prime，其中is_prime[i] = True表示数字i是质数后，第二步就是从中筛选出“纯质数”。

对于一个质数p，我们需要判断它的每一位数字是否都属于集合 {2, 3, 5, 7}。注意，这里有一个关键点：数字0和1不是质数，数字4， 6， 8， 9是合数。因此，合法的数字位只能是2， 3， 5， 7这四个一位数质数。

如何逐位获取一个整数的各个数字？常见的方法有两种：

1. 转换为字符串：将整数p转换为字符串str(p)，然后遍历字符串中的每个字符，判断其是否在[‘2‘， ‘3‘， ‘5‘， ‘7’]中。这种方法直观易懂。
2. 数学取余法：通过循环while p > 0:，每次用p % 10得到个位数，判断它是否在{2， 3， 5， 7}中，然后用p //= 10去掉个位。这种方法效率稍高，更体现算法思维。

两种方法在本题的数据规模下性能差异不大，可以根据个人喜好选择。将第一步和第二步结合起来，我们就能得到所有纯质数。

3. 代码实现与逐行精讲

理论清晰了，现在让我们把思路转化为代码。我会提供一个完整、健壮且带有详细注释的实现，并解释每一行代码的意图和可能遇到的坑。

3.1 埃拉托斯特尼筛法的Python实现

首先，我们实现核心的筛法。这里有一个重要的优化技巧：使用列表生成式初始化筛子，并且只筛选奇数，因为除了2以外的偶数都不是质数，这样可以节省一半的空间和时间。

def sieve_of_eratosthenes(limit): """ 埃拉托斯特尼筛法，返回一个布尔列表is_prime。 is_prime[i]为True表示数字i是质数。 """ if limit < 2: return [False] * (limit + 1) # 初始化假设所有数都是质数 is_prime = [True] * (limit + 1) is_prime[0] = is_prime[1] = False # 0和1不是质数 # 核心筛选过程：只需遍历到sqrt(limit) for i in range(2, int(limit ** 0.5) + 1): if is_prime[i]: # 从i*i开始标记，因为更小的倍数已经被之前的质数标记过了 # 步长为i，标记所有i的倍数 for j in range(i * i, limit + 1, i): is_prime[j] = False return is_prime

关键点解析：

• range(2, int(limit ** 0.5) + 1)：这是效率的关键。我们只需要用小于等于√limit的质数去筛选。
• if is_prime[i]:：只有当前数i仍然是质数时，才需要去标记它的倍数。如果i已经被标记为合数，那么它的倍数肯定已经被i的某个质因子标记过了。
• for j in range(i * i, limit + 1, i):：这里从i*i开始标记，而不是从2*i开始。为什么呢？因为对于质数i，2*i，3*i， ...，(i-1)*i这些数，它们一定有比i小的质因子（比如2， 3等），所以在之前遍历更小的质数时就已经被标记为合数了。从i*i开始可以避免重复操作。这是埃氏筛的一个经典优化。

3.2 纯质数判断函数

接下来，我们实现判断一个数是否为“纯质数”的函数。这里采用数学取余法，因为它不涉及字符串转换，理论上更纯粹。

def is_pure_prime(num, is_prime): """ 判断一个数是否为纯质数。 前提：is_prime数组已通过筛法生成，且num是质数。 """ # 首先，它必须本身是质数 if not is_prime[num]: return False # 处理数字的每一位 n = num while n > 0: digit = n % 10 # 获取个位数 # 如果某一位数字不是2，3，5，7中的一个，则不是纯质数 if digit not in {2, 3, 5, 7}: return False n //= 10 # 去掉个位 return True

注意：这个函数假设传入的is_prime数组是有效的，并且num在数组索引范围内。我们在主逻辑中会先确保num是质数，再调用此函数，但函数内部仍然保留了if not is_prime[num]的判断，这是一个良好的防御性编程习惯。

3.3 主程序逻辑与性能考量

现在，我们把两部分组合起来，并针对蓝桥杯真题的典型范围（比如1到N）进行求解。

def count_pure_primes(limit): """ 计算从1到limit（包含）范围内的纯质数个数。 """ # 1. 生成质数表 is_prime = sieve_of_eratosthenes(limit) count = 0 pure_prime_list = [] # 如果需要列出具体数，可以用这个列表 # 2. 遍历所有数，检查是否为纯质数 # 注意：除了2，其他偶数不可能为纯质数（因为包含非{2，3，5，7}的数字位） # 我们可以从质数开始遍历，或者简单遍历所有奇数加上2 for num in range(2, limit + 1): if is_prime[num] and is_pure_prime(num, is_prime): count += 1 pure_prime_list.append(num) return count, pure_prime_list if __name__ == "__main__": # 以蓝桥杯第十二届省赛真题范围为例 N = 20210605 total_count, primes = count_pure_primes(N) print(f"在1到{N}范围内，共有{total_count}个纯质数。") # 如果需要打印前20个看看 print(f"前20个纯质数分别是：{primes[:20]}")

性能与优化讨论：上面的主循环for num in range(2, limit + 1)遍历了所有数。一个明显的优化是：除了数字2，任何包含偶数位（0， 4， 6， 8）或数字5（除了它自身作为个位）的质数，都不可能是纯质数。但注意，5本身是质数且每一位（只有一位5）不符合{2，3，5，7}的条件吗？5在集合里，所以5是纯质数！同理，2也是纯质数。所以，更精确的优化是：我们可以只遍历那些每一位都可能是2，3，5，7的数。但这需要生成所有由这些数字组成的数，逻辑稍复杂。在千万量级下，直接遍历所有质数的开销是可以接受的（质数个数大约为N/ln(N)，约130万），而is_pure_prime判断很快。因此，为了代码清晰，首次实现可以不采用这个优化。

4. 算法优化与深入思考

在基本方案工作后，我们总是可以思考：还能更快吗？空间能更省吗？这里分享几个进阶的优化方向。

4.1 欧拉筛（线性筛）的应用

埃氏筛的时间复杂度是O(N log log N)，已经很快。但它存在一个瑕疵：有些合数会被它的多个质因子重复标记（例如6会被2和3各标记一次）。欧拉筛（也称线性筛）可以保证每个合数只被它的最小质因子标记一次，时间复杂度严格是O(N)。在处理极端数据或需要一次性获取质数列表时，欧拉筛是更好的选择。

def linear_sieve(limit): """ 欧拉筛（线性筛）法。 返回质数列表 primes。 """ is_prime = [True] * (limit + 1) primes = [] # 用于存储所有找到的质数 for i in range(2, limit + 1): if is_prime[i]: primes.append(i) # 关键步骤：用当前质数表里的数去标记合数 for p in primes: if i * p > limit: break is_prime[i * p] = False # 如果p是i的最小质因子，则停止标记，保证每个合数只被标记一次 if i % p == 0: break return primes, is_prime

使用欧拉筛后，我们的主循环可以遍历primes列表而不是整个范围，因为primes已经包含了所有质数，这进一步减少了需要检查的数的数量。

4.2 空间优化与位运算

当limit非常大（例如上亿）时，is_prime这个布尔列表会占用大量内存（每个元素一个字节）。一个常见的优化是使用位数组，例如Python的array(‘b‘)或者bytearray，甚至可以使用bitarray第三方库，将每个质数状态压缩到一个比特位，内存占用可以减少为原来的1/8。

此外，在判断“纯质数”时，我们可以预先计算好0-9这十个数字中哪些是“纯数字位”。

PURE_DIGITS = {2， 3， 5， 7} # 判断函数中直接使用 if digit not in PURE_DIGITS: ...

使用集合in操作的平均时间复杂度是O(1)，非常高效。

4.3 边界条件与特殊值处理

在编程竞赛中，边界条件往往是失分点。对于本题，需要特别注意：

1. 范围包含1：1不是质数，更不是纯质数。
2. 数字0：如果题目范围从0开始，0不是质数。
3. 最大值的处理：确保循环能正确覆盖到上限limit。
4. 单个数字的质数：2， 3， 5， 7 这四位本身都是一位数，且是质数，它们都是纯质数。这是容易忽略的四个答案。

在我们的实现中，sieve_of_eratosthenes函数已经正确处理了0和1的情况，主循环从2开始，这些都规避了边界问题。

5. 实战测试与常见“坑点”

写完代码，一定要用多种情况测试。我们可以构造一些小范围的测试用例来验证正确性。

5.1 构造测试用例

def test(): """测试函数""" # 测试1：小范围手工验证 test_limit = 100 count， primes = count_pure_primes(test_limit) print(f"1-{test_limit} 的纯质数有：{primes}") # 手工计算应该包含：2， 3， 5， 7， 23， 37， 53， 73 expected = [2， 3， 5， 7， 23， 37， 53， 73] assert primes == expected， f"测试失败！得到{primes}， 期望{expected}" print("小范围测试通过！") # 测试2：单个值测试 is_prime_arr = sieve_of_eratosthenes(100) assert is_pure_prime(23， is_prime_arr) == True assert is_pure_prime(29， is_prime_arr) == False # 9不是纯数字 assert is_pure_prime(1， is_prime_arr) == False assert is_pure_prime(2， is_prime_arr) == True print("单值测试通过！") # 测试3：性能测试（可选） import time start = time.time() limit = 10_000_000 # 一千万 is_prime = sieve_of_eratosthenes(limit) # 简单统计一下质数个数，验证筛法正确性 prime_count = sum(is_prime) print(f"1-{limit} 内质数个数（用于验证）：{prime_count}") print(f"筛法耗时：{time.time() - start:.2f}秒") if __name__ == "__main__": test() # 然后运行主程序 N = 20210605 total_count， _ = count_pure_primes(N) print(f"最终答案（1-{N}纯质数个数）：{total_count}")

5.2 竞赛中容易踩的“坑”

根据我的经验，在解决这类问题时，以下几个“坑”最容易让选手失分：

1. 超时（TLE）：这是最大的坑。直接对每个数使用试除法判断质数，在数据量大时必超时。必须使用筛法（埃氏筛或欧拉筛）进行预处理。
2. 内存超限（MLE）：如果使用[True] * (limit + 1)且limit很大（比如上亿），列表会占用几百MB内存。在内存限制严格的比赛中，需要考虑使用位数组优化，或者分块筛法。
3. 概念理解偏差：
   • 误判“1”：1不是质数。
   • 误判“0”：0不是质数，且任何包含0的数都不是纯质数。
   • 数字“5”和“2”：5和2本身是质数，且它们的单一位（5和2）在合法数字集{2，3，5，7}内，因此它们是纯质数。这一点容易被忽略。
4. 循环边界错误：
   • 在埃氏筛中，外层循环for i in range(2, int(limit**0.5)+1)，这里int(limit**0.5)+1必须包含，否则如果limit是一个完全平方数，其平方根质数可能无法被遍历到。
   • 内层标记倍数时，for j in range(i*i， limit+1， i)，注意i*i可能一开始就超过limit，Python的range会处理这种情况，但理解其含义很重要。
5. 输出格式错误：蓝桥杯通常是填空题或要求输出一个整数。务必确认题目要求是输出“个数”还是“列表”，或者求和。我们的函数设计为返回个数和列表，适应性较强。

6. 举一反三：类似问题与扩展

掌握了纯质数的解法，我们可以轻松应对一系列变体问题。这体现了算法思想的通用性。

6.1 变体问题示例

1. 绝对质数：将一个质数进行数位反转（如13反转为31），如果反转后的数也是质数，则称其为绝对质数。求解时需要同时判断原数和反转数。
2. 可截质数：从一个质数中，从左向右或从右向左连续截取数字，得到的每个数都是质数。例如3797，从左截取：3， 37， 379， 3797都是质数；从右截取：7， 97， 797， 3797也都是质数。这需要更复杂的递归或迭代检查。
3. 按位筛选的扩展：如果不是要求每位都是质数，而是要求每位满足其他条件（如都是偶数、都是奇数、数字之和为质数等），只需要修改is_pure_prime函数中的判断逻辑即可。

6.2 将筛法模块化

在实际项目或多次竞赛中，质数筛是一个高频工具。将其封装成一个可靠的函数或类是非常好的习惯。

class PrimeSieve: """一个质数筛工具类""" def __init__(self， limit): self.limit = limit self.is_prime = self._sieve(limit) self.prime_list = [i for i in range(2， limit+1) if self.is_prime[i]] def _sieve(self， limit): """内部使用的埃氏筛""" is_prime = [True] * (limit + 1) is_prime[0] = is_prime[1] = False for i in range(2， int(limit**0.5)+1): if is_prime[i]: for j in range(i*i， limit+1， i): is_prime[j] = False return is_prime def is_prime_num(self， n): """判断单个数是否为质数（需在limit范围内）""" if 0 <= n <= self.limit: return self.is_prime[n] else: # 如果超出预计算范围，则回退到试除法（仅适用于不大的数） if n < 2: return False for i in range(2， int(n**0.5)+1): if n % i == 0: return False return True # 使用示例 sieve = PrimeSieve(10_000_000) if sieve.is_prime_num(999983): print("999983 在千万以内是质数") print(f"千万以内质数个数：{len(sieve.prime_list)}")

这样，我们就把质数相关的功能封装起来，后续解题时可以直接调用，避免重复编写筛法代码，既提高了效率，也减少了出错的可能。

回过头看，“纯质数”这个问题就像一个精致的引子，它把基础的数论知识和编程技巧串联起来。解决它的过程，本质上是在训练我们将复杂问题分解为已知模块（质数判断、数字位分离）并组合解决的能力。在竞赛和实际开发中，这种能力远比记忆某个特定算法更重要。我个人的习惯是，每解决一道这样的题，都会问自己：它的核心考点是什么？有哪些变体？我封装的工具函数能否复用到其他地方？经过这样的思考，代码才不会白写，能力才能真正沉淀下来。