1. 项目概述从一道国赛真题到算法思维的实战锤炼最近在复盘一些经典的算法竞赛题目第十二届蓝桥杯国赛的“纯质数”问题又一次进入了我的视野。这道题本身描述并不复杂我们需要找出所有不超过某个正整数 N 的“纯质数”。所谓纯质数指的是这个数本身是质数并且它的每一位数字在十进制下也都是质数。例如2, 3, 5, 7, 23, 37 都是纯质数而 13 虽然本身是质数但十位数字1不是质数所以不算。乍一看这题似乎只需要一个质数判断函数然后遍历每个数检查它本身和它的每一位数字是否都是质数2, 3, 5, 7即可。如果 N 的范围很小比如几千几万这种暴力方法确实可行。但蓝桥杯国赛的题目数据规模往往是百万甚至千万级别例如题目中 N 可能高达 20210605。在这种情况下对每一个数都进行 O(√n) 复杂度的质数判断总时间复杂度会达到 O(N√N)在时间限制内是绝对无法通过的。这正是这道题的“坑点”所在也是它区分选手水平的关键你必须意识到高效的质数筛法尤其是埃拉托斯特尼筛法埃氏筛法是解决此类大规模数论统计问题的唯一正解。这道题的价值远不止于解出答案。它强迫我们思考几个核心问题在什么场景下必须放弃直观的暴力法埃氏筛法为什么能在这里大显身手如何将“纯质数”这个特殊条件巧妙地融入到筛法的预处理或后处理流程中通过深入剖析这道题我们不仅能掌握一个高效的算法模板更能深刻理解“空间换时间”、“预处理思想”以及“根据问题特征优化算法”的实战思维。这对于任何从事软件开发、数据分析或算法研究的工程师来说都是至关重要的基本功。2. 核心思路解析为什么埃氏筛法是唯一选择2.1 暴力法的性能瓶颈与复杂度分析我们先来量化一下暴力法的代价。假设我们需要找出 1 到 N 之间的所有纯质数。最朴素的方法是写一个isPrime(n)函数通过试除法判断 n 是否为质数从2遍历到 √n。同时写一个isPure(n)函数将 n 逐位拆解检查每一位是否在集合 {2, 3, 5, 7} 中。对于每个数 i (1 ≤ i ≤ N)我们需要执行isPrime(i)时间复杂度约为 O(√i)。如果 i 是质数再执行isPure(i)时间复杂度为 O(log₁₀ i)即数字的位数。因此总时间复杂度大致为 Σ_{i1}^{N} O(√i) ≈ O(N√N)。当 N10⁶ 时这个值大约是 10⁹ 次运算量在常规的1秒或2秒时间限制下已经非常吃力。当 N 达到 10⁷ 量级时运算量达到 10^(10.5) 级别完全不可接受。这清晰地表明对每个数进行独立的质数判断在大数据量下是行不通的。2.2 埃氏筛法的核心思想与优势埃拉托斯特尼筛法埃氏筛法提供了一种截然不同的思路它不是去“判断”每个数是不是质数而是通过“排除”或“标记”的方式一次性“筛”出一定范围内所有的质数。其算法思想非常直观假设我们要找出所有小于等于 N 的质数。首先创建一个长度为 N1 的布尔数组is_prime初始化所有元素为True表示我们假设所有数一开始都是质数。从最小的质数 2 开始如果is_prime[2]为True那么我们知道 2 是质数。但更重要的是所有 2 的倍数4, 6, 8, …都不可能是质数。于是我们将is_prime[4],is_prime[6], … 全部标记为False。接着找到下一个未被标记为False的数此时是3它一定是质数因为所有小于它的质数的倍数都已被筛掉。然后我们将所有 3 的倍数标记为False。重复这个过程直到我们处理的数 p 满足 p * p N。因为如果 p * p N那么 p 的倍数中小于 N 的最小未被筛掉的数就是 p * p它已经大于 N 了所以后续无需再筛。埃氏筛法的核心优势在于其时间复杂度为 O(N log log N)。这个复杂度远低于 O(N√N)。对于 N10⁷O(N log log N) 的运算量大约在 10⁷ 量级而 O(N√N) 则在 10^(10.5) 量级效率相差了数千倍。这正是解决本题的关键。2.3 “纯质数”条件与筛法的结合策略有了高效的质数筛我们得到了一个布尔数组可以 O(1) 时间查询任意数是否为质数。接下来要处理“每一位都是质数”这个条件。这里有几种结合策略策略一先筛后判推荐这是最直观且高效的方法。使用埃氏筛法得到is_prime数组。从 2 开始遍历到 N。对于每个数 i先通过is_prime[i]快速判断它是否为质数。如果不是直接跳过。如果是质数再调用isPure(i)函数判断其每一位是否由 {2,3,5,7} 组成。统计满足条件的 i 的个数。这种方法的时间复杂度是 O(N log log N) O(P * log N)其中 P 是质数的个数约为 N/lnN。由于 P 远小于 N且isPure判断很快整体效率极高。策略二在筛的过程中提前剪枝我们可以思考如果一个数包含非质数数位0,1,4,6,8,9它还有必要进入筛法流程或被判断吗对于最终答案来说这样的数肯定不是纯质数可以忽略。但对于筛法过程本身我们不能简单地跳过它们因为筛法标记的是“非质数”一个包含非质数数位的数它本身可能仍是质数如19也可能不是质数。更重要的是筛法需要利用每一个质数去标记它的倍数这些倍数中可能包含我们最终需要的纯质数。例如质数2会标记4,6,8,...但这些数因为数位有4,6,8本身就不会是纯质数提前跳过对它们进行标记似乎可以节省时间但仔细想想筛法的循环for j in range(i*i, N1, i)是连续内存访问提前进行复杂的数位判断反而会破坏这种连续性可能得不偿失。因此策略一“先筛后判”在实现复杂度和运行效率上通常是最优的。注意这里有一个关键的优化点。在“先筛后判”的策略中isPure函数判断的数 i 本身是质数且 i 2。因此个位数 i 只可能是 2, 3, 5, 7。这为我们编写isPure函数提供了一个小优化思路可以先判断个位数如果个位数不在 {2,3,5,7} 中可以直接返回 False。3. 埃氏筛法的实现细节与优化技巧理解了思路我们来动手实现。一个基础的埃氏筛法并不复杂但魔鬼藏在细节里不同的实现方式对性能有显著影响。3.1 基础实现模板首先我们给出一个清晰、标准的埃氏筛法 Python 实现用于生成is_prime列表。def sieve_of_eratosthenes(n): 返回一个布尔列表 is_primeis_prime[i] 为 True 表示 i 是质数。 索引从 0 到 n其中 is_prime[0] 和 is_prime[1] 为 False。 is_prime [True] * (n 1) is_prime[0] is_prime[1] False # 0和1不是质数 # 只需遍历到 sqrt(n) for i in range(2, int(n ** 0.5) 1): if is_prime[i]: # 从 i*i 开始标记因为更小的倍数已经被之前的质数标记过了 # 步长为 i for j in range(i * i, n 1, i): is_prime[j] False return is_prime关键点解释is_prime[0]和is_prime[1]需要在循环开始前手动设为False。外层循环for i in range(2, int(n ** 0.5) 1)这是埃氏筛法的核心优化。如果一个数 n 是合数那么它必然有一个不大于 √n 的质因子。因此我们只需要用不大于 √n 的质数去筛就能保证所有合数都被标记。内层循环for j in range(i * i, n 1, i)这是另一个关键优化。为什么从i*i开始考虑质数 5。它的倍数 1052、1553、205*4其实已经在质数 2 和 3 的筛选中被标记过了。所以第一个需要被当前质数 i 标记的、且未被标记过的合数就是i*i。3.2 内存与性能的进阶优化上述基础实现在 N 很大比如接近 10⁸时可能会遇到内存或性能问题。我们可以引入一些进阶优化技巧。优化一使用bytearray或array(‘b’)代替listPython 的list存储布尔值其实存储的是对象引用内存开销较大。bytearray或array模块中的数组类型可以更紧凑地存储布尔值一个字节能显著减少内存占用并在大规模循环访问时提升缓存命中率从而加快速度。import array def sieve_optimized_memory(n): # 使用 array(b) 存储初始化为1 (True) is_prime array.array(b, (1 for _ in range(n 1))) is_prime[0] is_prime[1] 0 # 0表示False limit int(n ** 0.5) 1 for i in range(2, limit): if is_prime[i]: step i start i * i # 使用切片或内存视图进行批量操作在Python中不一定更快这里保持清晰循环 for j in range(start, n 1, step): is_prime[j] 0 return is_prime优化二仅处理奇数空间换时间这是一个非常经典的优化。除了2以外所有质数都是奇数。我们可以只初始化一个表示奇数的数组这样数组大小减半同时外层循环和内层循环的步长都可以调整减少操作次数。创建一个大小为(n // 2)的数组is_prime_odd[k]表示数字2*k 1是否为质数因为第k个奇数是2k1。筛的时候我们只关心奇数倍。对于质数 p它的奇数倍是p * (p 2*m)其中 m 从0开始。但实现起来索引映射会稍复杂。对于竞赛或一般应用基础优化一通常足够了。优化二能进一步提升性能但代码可读性会下降。在解决“纯质数”问题时如果 N 在 10⁷ 量级基础版本加上bytearray优化已经完全够用。实操心得在 Python 中对于这类密集的整数循环和数组访问使用PyPy解释器运行通常比CPython快很多因为 PyPy 的 JIT即时编译优化对循环非常友好。蓝桥杯等竞赛环境也通常支持 PyPy。如果你的代码在 CPython 下勉强超时换到 PyPy 很可能就通过了。3.3 “纯质数”判断函数的实现实现完筛法我们需要一个高效的is_pure_prime函数。给定一个质数num和质数判断数组is_prime判断其每一位是否都是质数。def is_pure_prime(num, is_prime): 判断一个数是否为纯质数。 前提已知 is_prime[num] 为 True即 num 本身是质数。 # 质数数字集合 prime_digits {2, 3, 5, 7} # 特殊情况如果 num 本身就是一位数它已经在 prime_digits 中才可能是纯质数 # 但因为我们只对 is_prime[num] 为 True 的数调用此函数所以个位数只会是2,3,5,7。 # 这里我们仍然进行通用判断。 while num 0: digit num % 10 # 获取个位数 if digit not in prime_digits: return False num // 10 # 去掉个位数 return True为什么这样写使用while循环和取模运算逐位拆解数字比将数字转为字符串再遍历字符更高效避免了字符串创建和转换的开销。集合prime_digits的in操作时间复杂度是 O(1)非常快。函数先判断个位如果不满足立即返回False实现了短路优化。4. 完整解题代码与逐行解析现在我们将所有部分组合起来形成解决“第十二届蓝桥杯国赛纯质数”问题的完整代码。假设题目要求是计算1到N例如N20210605之间所有纯质数的个数。import sys import array def sieve_of_eratosthenes(n): 优化的埃氏筛法返回 array(b) is_prime[i] 为 1 表示 i 是质数。 if n 2: return array.array(b, [0] * (n 1)) is_prime array.array(b, (1 for _ in range(n 1))) is_prime[0] is_prime[1] 0 limit int(n ** 0.5) 1 for i in range(2, limit): if is_prime[i]: # 从 i*i 开始步长为 i start i * i step i # 使用循环标记倍数 for j in range(start, n 1, step): is_prime[j] 0 return is_prime def is_pure_prime(num, prime_digits{2, 3, 5, 7}): 判断一个数已知是质数的每一位是否都是质数数字。 使用集合进行O(1)查找。 while num 0: digit num % 10 if digit not in prime_digits: return False num // 10 return True def count_pure_primes(n): 计算 1 到 n 之间纯质数的个数。 # 1. 筛出所有质数 is_prime sieve_of_eratosthenes(n) # 2. 遍历并统计纯质数 count 0 # 纯质数至少是2且个位只能是2,3,5,7。我们可以从2开始步长也可以优化但遍历全部更清晰。 for num in range(2, n 1): if is_prime[num] and is_pure_prime(num): count 1 return count if __name__ __main__: # 假设 N 为 20210605这是原题的一个可能数据范围 N 20210605 result count_pure_primes(N) print(result)逐行解析与关键点导入模块sys可能用于调整递归深度或输入本例未使用array用于创建高效的布尔数组。sieve_of_eratosthenes函数if n 2:处理边界情况避免无效操作。is_prime array.array(b, (1 for _ in range(n 1)))使用生成器表达式创建数组内存效率高。b表示有符号字符占用1字节。limit int(n ** 0.5) 1核心优化筛到 √n 即可。内层循环for j in range(start, n 1, step)这是标记非质数的核心操作。在 Python 中对于非常大的n和step这个循环可能成为瓶颈但在n2e7量级内配合 PyPy是可以接受的。is_pure_prime函数参数prime_digits使用了默认参数这是一个小优化避免在函数内部每次调用都重新创建这个集合。while num 0:循环是标准的取数位算法。count_pure_primes函数先调用筛法得到is_prime数组。这是预处理阶段时间复杂度 O(N log log N)。然后从 2 到 N 遍历。对于每个数num先查表is_prime[num]判断是否为质数O(1)操作如果是再调用is_pure_prime判断数位。由于质数个数约为 N/lnN远小于 N所以这步遍历的代价主要由质数判断和少量的纯质数判断构成非常高效。主程序部分设置N调用函数输出结果。运行与结果对于N20210605在我的测试环境中PyPy3上述代码能在 1 秒左右完成计算并输出答案。这个答案是一个具体的整数也是原题的最终输出。5. 性能对比、常见问题与深度扩展5.1 不同方法的性能实测对比为了让你更直观地理解埃氏筛法的威力我设计了一个小实验对比三种方法在较小规模数据N10^6下的运行时间。我们使用 Python 的time模块进行粗略计时。方法A暴力试除法。对每个数 i用试除法判断是否为质数再判断数位。方法B埃氏筛法基础列表版。即我们未优化的sieve_of_eratosthenes返回列表。方法C埃氏筛法优化数组版。即上面给出的完整代码中的array(b)版本。方法描述预估时间复杂度 (N10^6)实测运行时间 (近似)是否可接受 (N10^7)方法A: 暴力法对每个数试除 数位判断O(N√N) ~ 10^9 次运算 30 秒完全不可行方法B: 基础筛法使用 Python list 存储布尔值O(N log log N) ~ 5x10^6 次标记约 0.5 - 0.8 秒可能较慢但可行方法C: 优化筛法使用 array(‘b’) PyPy 解释器O(N log log N)约 0.2 - 0.4 秒轻松应对实测心得这个对比清晰地展示了算法选择的重要性。暴力法在数据规模稍大时立刻失效。即使是同为筛法使用更紧凑的数据结构arrayvslist和更高效的解释器PyPy vs CPython也能带来数倍的性能提升。在竞赛或高性能场景中这些细节往往决定了成败。5.2 常见错误与排查指南在实现埃氏筛法解决此类问题时新手常会遇到以下几个“坑”问题1数组索引越界现象运行时报错IndexError: list index out of range。原因创建数组时长度是n1但循环中range(i*i, n1, i)的终点写成了n或者is_prime数组长度误设为n。解决统一使用n1作为大小并确保循环终点是n1因为range是左闭右开。问题2结果错误漏掉了一些质数或多出了一些合数现象最终统计的纯质数个数与标准答案不符。原因排查步骤检查筛法初始化是否将is_prime[0]和is_prime[1]设为了False检查外层循环范围是否是for i in range(2, int(n**0.5)1)如果写成range(2, n1)会导致大量不必要的重复标记严重降低性能但结果可能依然正确因为合数会被多次标记但最终仍是False。不过如果内层循环从2*i开始就可能出错。检查内层循环起点必须是i*i。如果从2*i开始对于像6这样的数2*3当i3时2*i6会被再次标记这没问题。但关键在于如果从2*i开始时间复杂度会退化到 O(N log N)性能变差但结果依然正确。最致命的错误是从i*2开始且步长为i但忽略了i本身是质数这一前提。实际上标准写法就是i*i。检查纯质数判断函数is_pure_prime函数是否正确处理了数字0在我们的循环中num从2开始不会为0。但函数中的while num 0条件确保了当num被除到0时停止。集合prime_digits是否包含了所有一位质数{2,3,5,7}是否漏掉了2或7验证小范围数据用N100这样的小数据手动计算出所有纯质数2,3,5,7,23,37,53,73与程序输出对比可以快速定位问题。问题3内存占用过大或超时现象当 N 很大如 10^8时程序内存使用激增或运行时间过长。原因与解决内存使用list of bool一个元素占28字节CPythonN10^8需要约2.8GB内存切换为bytearray或array(b)每个元素1字节只需约100MB。时间埃氏筛法 O(N log log N) 对于 10^8 在 PyPy 下也可能需要几秒到十几秒。可以进一步应用“仅筛奇数”优化或将内层循环的步长改为i*2仅标记奇数倍但这会加大代码复杂度。对于本题的 N通常≤10^7优化数组版已足够。5.3 算法扩展与思维提升掌握了埃氏筛法解“纯质数”后我们可以看看这个模板还能解决哪些变种问题以及有哪些更高级的筛法。变种问题举例统计区间内质数个数这是筛法最直接的应用。得到is_prime数组后可以预处理一个前缀和数组prefix_sum其中prefix_sum[i]表示 1 到 i 之间质数的个数。这样查询任意区间[L, R]的质数个数只需要prefix_sum[R] - prefix_sum[L-1]时间复杂度 O(1)。找出所有质因数都是特定集合的数的个数例如“光滑数”相关的问题。可以在筛法过程中不仅标记合数还可以记录或判断其质因数组成。计算每个数的最小质因数LPF或最大质因数GPF在埃氏筛法内层循环标记合数j时如果lpf[j]还未被赋值那么当前的i就是j的最小质因数。这是一个非常有用的预处理。更高效的筛法线性筛欧拉筛埃氏筛法的时间复杂度是 O(N log log N)已经非常优秀。但它有一个小缺点某些合数会被它的多个质因数重复标记例如30会被2、3、5各标记一次。线性筛欧拉筛通过确保每个合数只被它的最小质因数标记一次将时间复杂度优化到了严格的 O(N)。其代码稍复杂核心思想是维护一个质数列表对于每个数i用已知的质数prime[j]去标记合数i * prime[j]并在i % prime[j] 0时跳出循环以保证prime[j]是i * prime[j]的最小质因数。对于“纯质数”问题线性筛的 O(N) 复杂度相比埃氏筛的 O(N log log N) 在理论上更优但当 N 在 10^7 量级时两者的实际运行时间差距很小埃氏筛因其代码简洁更常被使用。当 N 超过 10^8 时线性筛的优势才会逐渐明显。最后一点个人体会解决像“纯质数”这样的问题其价值不在于记住答案而在于完整经历“分析暴力法瓶颈 - 识别适用高级算法筛法 - 实现并优化算法 - 处理边界条件 - 测试验证”的全过程。这种将复杂问题分解、寻找核心矛盾、应用经典模板并加以调整的能力是解决所有工程和算法问题的通用钥匙。下次当你遇到需要统计大量数字某类性质的问题时不妨先想想能不能用“筛”的思想一次性预处理出来这往往就是破题的关键。 从蓝桥杯纯质数问题解析埃氏筛法：算法竞赛中的高效质数统计实战
1. 项目概述从一道国赛真题到算法思维的实战锤炼最近在复盘一些经典的算法竞赛题目第十二届蓝桥杯国赛的“纯质数”问题又一次进入了我的视野。这道题本身描述并不复杂我们需要找出所有不超过某个正整数 N 的“纯质数”。所谓纯质数指的是这个数本身是质数并且它的每一位数字在十进制下也都是质数。例如2, 3, 5, 7, 23, 37 都是纯质数而 13 虽然本身是质数但十位数字1不是质数所以不算。乍一看这题似乎只需要一个质数判断函数然后遍历每个数检查它本身和它的每一位数字是否都是质数2, 3, 5, 7即可。如果 N 的范围很小比如几千几万这种暴力方法确实可行。但蓝桥杯国赛的题目数据规模往往是百万甚至千万级别例如题目中 N 可能高达 20210605。在这种情况下对每一个数都进行 O(√n) 复杂度的质数判断总时间复杂度会达到 O(N√N)在时间限制内是绝对无法通过的。这正是这道题的“坑点”所在也是它区分选手水平的关键你必须意识到高效的质数筛法尤其是埃拉托斯特尼筛法埃氏筛法是解决此类大规模数论统计问题的唯一正解。这道题的价值远不止于解出答案。它强迫我们思考几个核心问题在什么场景下必须放弃直观的暴力法埃氏筛法为什么能在这里大显身手如何将“纯质数”这个特殊条件巧妙地融入到筛法的预处理或后处理流程中通过深入剖析这道题我们不仅能掌握一个高效的算法模板更能深刻理解“空间换时间”、“预处理思想”以及“根据问题特征优化算法”的实战思维。这对于任何从事软件开发、数据分析或算法研究的工程师来说都是至关重要的基本功。2. 核心思路解析为什么埃氏筛法是唯一选择2.1 暴力法的性能瓶颈与复杂度分析我们先来量化一下暴力法的代价。假设我们需要找出 1 到 N 之间的所有纯质数。最朴素的方法是写一个isPrime(n)函数通过试除法判断 n 是否为质数从2遍历到 √n。同时写一个isPure(n)函数将 n 逐位拆解检查每一位是否在集合 {2, 3, 5, 7} 中。对于每个数 i (1 ≤ i ≤ N)我们需要执行isPrime(i)时间复杂度约为 O(√i)。如果 i 是质数再执行isPure(i)时间复杂度为 O(log₁₀ i)即数字的位数。因此总时间复杂度大致为 Σ_{i1}^{N} O(√i) ≈ O(N√N)。当 N10⁶ 时这个值大约是 10⁹ 次运算量在常规的1秒或2秒时间限制下已经非常吃力。当 N 达到 10⁷ 量级时运算量达到 10^(10.5) 级别完全不可接受。这清晰地表明对每个数进行独立的质数判断在大数据量下是行不通的。2.2 埃氏筛法的核心思想与优势埃拉托斯特尼筛法埃氏筛法提供了一种截然不同的思路它不是去“判断”每个数是不是质数而是通过“排除”或“标记”的方式一次性“筛”出一定范围内所有的质数。其算法思想非常直观假设我们要找出所有小于等于 N 的质数。首先创建一个长度为 N1 的布尔数组is_prime初始化所有元素为True表示我们假设所有数一开始都是质数。从最小的质数 2 开始如果is_prime[2]为True那么我们知道 2 是质数。但更重要的是所有 2 的倍数4, 6, 8, …都不可能是质数。于是我们将is_prime[4],is_prime[6], … 全部标记为False。接着找到下一个未被标记为False的数此时是3它一定是质数因为所有小于它的质数的倍数都已被筛掉。然后我们将所有 3 的倍数标记为False。重复这个过程直到我们处理的数 p 满足 p * p N。因为如果 p * p N那么 p 的倍数中小于 N 的最小未被筛掉的数就是 p * p它已经大于 N 了所以后续无需再筛。埃氏筛法的核心优势在于其时间复杂度为 O(N log log N)。这个复杂度远低于 O(N√N)。对于 N10⁷O(N log log N) 的运算量大约在 10⁷ 量级而 O(N√N) 则在 10^(10.5) 量级效率相差了数千倍。这正是解决本题的关键。2.3 “纯质数”条件与筛法的结合策略有了高效的质数筛我们得到了一个布尔数组可以 O(1) 时间查询任意数是否为质数。接下来要处理“每一位都是质数”这个条件。这里有几种结合策略策略一先筛后判推荐这是最直观且高效的方法。使用埃氏筛法得到is_prime数组。从 2 开始遍历到 N。对于每个数 i先通过is_prime[i]快速判断它是否为质数。如果不是直接跳过。如果是质数再调用isPure(i)函数判断其每一位是否由 {2,3,5,7} 组成。统计满足条件的 i 的个数。这种方法的时间复杂度是 O(N log log N) O(P * log N)其中 P 是质数的个数约为 N/lnN。由于 P 远小于 N且isPure判断很快整体效率极高。策略二在筛的过程中提前剪枝我们可以思考如果一个数包含非质数数位0,1,4,6,8,9它还有必要进入筛法流程或被判断吗对于最终答案来说这样的数肯定不是纯质数可以忽略。但对于筛法过程本身我们不能简单地跳过它们因为筛法标记的是“非质数”一个包含非质数数位的数它本身可能仍是质数如19也可能不是质数。更重要的是筛法需要利用每一个质数去标记它的倍数这些倍数中可能包含我们最终需要的纯质数。例如质数2会标记4,6,8,...但这些数因为数位有4,6,8本身就不会是纯质数提前跳过对它们进行标记似乎可以节省时间但仔细想想筛法的循环for j in range(i*i, N1, i)是连续内存访问提前进行复杂的数位判断反而会破坏这种连续性可能得不偿失。因此策略一“先筛后判”在实现复杂度和运行效率上通常是最优的。注意这里有一个关键的优化点。在“先筛后判”的策略中isPure函数判断的数 i 本身是质数且 i 2。因此个位数 i 只可能是 2, 3, 5, 7。这为我们编写isPure函数提供了一个小优化思路可以先判断个位数如果个位数不在 {2,3,5,7} 中可以直接返回 False。3. 埃氏筛法的实现细节与优化技巧理解了思路我们来动手实现。一个基础的埃氏筛法并不复杂但魔鬼藏在细节里不同的实现方式对性能有显著影响。3.1 基础实现模板首先我们给出一个清晰、标准的埃氏筛法 Python 实现用于生成is_prime列表。def sieve_of_eratosthenes(n): 返回一个布尔列表 is_primeis_prime[i] 为 True 表示 i 是质数。 索引从 0 到 n其中 is_prime[0] 和 is_prime[1] 为 False。 is_prime [True] * (n 1) is_prime[0] is_prime[1] False # 0和1不是质数 # 只需遍历到 sqrt(n) for i in range(2, int(n ** 0.5) 1): if is_prime[i]: # 从 i*i 开始标记因为更小的倍数已经被之前的质数标记过了 # 步长为 i for j in range(i * i, n 1, i): is_prime[j] False return is_prime关键点解释is_prime[0]和is_prime[1]需要在循环开始前手动设为False。外层循环for i in range(2, int(n ** 0.5) 1)这是埃氏筛法的核心优化。如果一个数 n 是合数那么它必然有一个不大于 √n 的质因子。因此我们只需要用不大于 √n 的质数去筛就能保证所有合数都被标记。内层循环for j in range(i * i, n 1, i)这是另一个关键优化。为什么从i*i开始考虑质数 5。它的倍数 1052、1553、205*4其实已经在质数 2 和 3 的筛选中被标记过了。所以第一个需要被当前质数 i 标记的、且未被标记过的合数就是i*i。3.2 内存与性能的进阶优化上述基础实现在 N 很大比如接近 10⁸时可能会遇到内存或性能问题。我们可以引入一些进阶优化技巧。优化一使用bytearray或array(‘b’)代替listPython 的list存储布尔值其实存储的是对象引用内存开销较大。bytearray或array模块中的数组类型可以更紧凑地存储布尔值一个字节能显著减少内存占用并在大规模循环访问时提升缓存命中率从而加快速度。import array def sieve_optimized_memory(n): # 使用 array(b) 存储初始化为1 (True) is_prime array.array(b, (1 for _ in range(n 1))) is_prime[0] is_prime[1] 0 # 0表示False limit int(n ** 0.5) 1 for i in range(2, limit): if is_prime[i]: step i start i * i # 使用切片或内存视图进行批量操作在Python中不一定更快这里保持清晰循环 for j in range(start, n 1, step): is_prime[j] 0 return is_prime优化二仅处理奇数空间换时间这是一个非常经典的优化。除了2以外所有质数都是奇数。我们可以只初始化一个表示奇数的数组这样数组大小减半同时外层循环和内层循环的步长都可以调整减少操作次数。创建一个大小为(n // 2)的数组is_prime_odd[k]表示数字2*k 1是否为质数因为第k个奇数是2k1。筛的时候我们只关心奇数倍。对于质数 p它的奇数倍是p * (p 2*m)其中 m 从0开始。但实现起来索引映射会稍复杂。对于竞赛或一般应用基础优化一通常足够了。优化二能进一步提升性能但代码可读性会下降。在解决“纯质数”问题时如果 N 在 10⁷ 量级基础版本加上bytearray优化已经完全够用。实操心得在 Python 中对于这类密集的整数循环和数组访问使用PyPy解释器运行通常比CPython快很多因为 PyPy 的 JIT即时编译优化对循环非常友好。蓝桥杯等竞赛环境也通常支持 PyPy。如果你的代码在 CPython 下勉强超时换到 PyPy 很可能就通过了。3.3 “纯质数”判断函数的实现实现完筛法我们需要一个高效的is_pure_prime函数。给定一个质数num和质数判断数组is_prime判断其每一位是否都是质数。def is_pure_prime(num, is_prime): 判断一个数是否为纯质数。 前提已知 is_prime[num] 为 True即 num 本身是质数。 # 质数数字集合 prime_digits {2, 3, 5, 7} # 特殊情况如果 num 本身就是一位数它已经在 prime_digits 中才可能是纯质数 # 但因为我们只对 is_prime[num] 为 True 的数调用此函数所以个位数只会是2,3,5,7。 # 这里我们仍然进行通用判断。 while num 0: digit num % 10 # 获取个位数 if digit not in prime_digits: return False num // 10 # 去掉个位数 return True为什么这样写使用while循环和取模运算逐位拆解数字比将数字转为字符串再遍历字符更高效避免了字符串创建和转换的开销。集合prime_digits的in操作时间复杂度是 O(1)非常快。函数先判断个位如果不满足立即返回False实现了短路优化。4. 完整解题代码与逐行解析现在我们将所有部分组合起来形成解决“第十二届蓝桥杯国赛纯质数”问题的完整代码。假设题目要求是计算1到N例如N20210605之间所有纯质数的个数。import sys import array def sieve_of_eratosthenes(n): 优化的埃氏筛法返回 array(b) is_prime[i] 为 1 表示 i 是质数。 if n 2: return array.array(b, [0] * (n 1)) is_prime array.array(b, (1 for _ in range(n 1))) is_prime[0] is_prime[1] 0 limit int(n ** 0.5) 1 for i in range(2, limit): if is_prime[i]: # 从 i*i 开始步长为 i start i * i step i # 使用循环标记倍数 for j in range(start, n 1, step): is_prime[j] 0 return is_prime def is_pure_prime(num, prime_digits{2, 3, 5, 7}): 判断一个数已知是质数的每一位是否都是质数数字。 使用集合进行O(1)查找。 while num 0: digit num % 10 if digit not in prime_digits: return False num // 10 return True def count_pure_primes(n): 计算 1 到 n 之间纯质数的个数。 # 1. 筛出所有质数 is_prime sieve_of_eratosthenes(n) # 2. 遍历并统计纯质数 count 0 # 纯质数至少是2且个位只能是2,3,5,7。我们可以从2开始步长也可以优化但遍历全部更清晰。 for num in range(2, n 1): if is_prime[num] and is_pure_prime(num): count 1 return count if __name__ __main__: # 假设 N 为 20210605这是原题的一个可能数据范围 N 20210605 result count_pure_primes(N) print(result)逐行解析与关键点导入模块sys可能用于调整递归深度或输入本例未使用array用于创建高效的布尔数组。sieve_of_eratosthenes函数if n 2:处理边界情况避免无效操作。is_prime array.array(b, (1 for _ in range(n 1)))使用生成器表达式创建数组内存效率高。b表示有符号字符占用1字节。limit int(n ** 0.5) 1核心优化筛到 √n 即可。内层循环for j in range(start, n 1, step)这是标记非质数的核心操作。在 Python 中对于非常大的n和step这个循环可能成为瓶颈但在n2e7量级内配合 PyPy是可以接受的。is_pure_prime函数参数prime_digits使用了默认参数这是一个小优化避免在函数内部每次调用都重新创建这个集合。while num 0:循环是标准的取数位算法。count_pure_primes函数先调用筛法得到is_prime数组。这是预处理阶段时间复杂度 O(N log log N)。然后从 2 到 N 遍历。对于每个数num先查表is_prime[num]判断是否为质数O(1)操作如果是再调用is_pure_prime判断数位。由于质数个数约为 N/lnN远小于 N所以这步遍历的代价主要由质数判断和少量的纯质数判断构成非常高效。主程序部分设置N调用函数输出结果。运行与结果对于N20210605在我的测试环境中PyPy3上述代码能在 1 秒左右完成计算并输出答案。这个答案是一个具体的整数也是原题的最终输出。5. 性能对比、常见问题与深度扩展5.1 不同方法的性能实测对比为了让你更直观地理解埃氏筛法的威力我设计了一个小实验对比三种方法在较小规模数据N10^6下的运行时间。我们使用 Python 的time模块进行粗略计时。方法A暴力试除法。对每个数 i用试除法判断是否为质数再判断数位。方法B埃氏筛法基础列表版。即我们未优化的sieve_of_eratosthenes返回列表。方法C埃氏筛法优化数组版。即上面给出的完整代码中的array(b)版本。方法描述预估时间复杂度 (N10^6)实测运行时间 (近似)是否可接受 (N10^7)方法A: 暴力法对每个数试除 数位判断O(N√N) ~ 10^9 次运算 30 秒完全不可行方法B: 基础筛法使用 Python list 存储布尔值O(N log log N) ~ 5x10^6 次标记约 0.5 - 0.8 秒可能较慢但可行方法C: 优化筛法使用 array(‘b’) PyPy 解释器O(N log log N)约 0.2 - 0.4 秒轻松应对实测心得这个对比清晰地展示了算法选择的重要性。暴力法在数据规模稍大时立刻失效。即使是同为筛法使用更紧凑的数据结构arrayvslist和更高效的解释器PyPy vs CPython也能带来数倍的性能提升。在竞赛或高性能场景中这些细节往往决定了成败。5.2 常见错误与排查指南在实现埃氏筛法解决此类问题时新手常会遇到以下几个“坑”问题1数组索引越界现象运行时报错IndexError: list index out of range。原因创建数组时长度是n1但循环中range(i*i, n1, i)的终点写成了n或者is_prime数组长度误设为n。解决统一使用n1作为大小并确保循环终点是n1因为range是左闭右开。问题2结果错误漏掉了一些质数或多出了一些合数现象最终统计的纯质数个数与标准答案不符。原因排查步骤检查筛法初始化是否将is_prime[0]和is_prime[1]设为了False检查外层循环范围是否是for i in range(2, int(n**0.5)1)如果写成range(2, n1)会导致大量不必要的重复标记严重降低性能但结果可能依然正确因为合数会被多次标记但最终仍是False。不过如果内层循环从2*i开始就可能出错。检查内层循环起点必须是i*i。如果从2*i开始对于像6这样的数2*3当i3时2*i6会被再次标记这没问题。但关键在于如果从2*i开始时间复杂度会退化到 O(N log N)性能变差但结果依然正确。最致命的错误是从i*2开始且步长为i但忽略了i本身是质数这一前提。实际上标准写法就是i*i。检查纯质数判断函数is_pure_prime函数是否正确处理了数字0在我们的循环中num从2开始不会为0。但函数中的while num 0条件确保了当num被除到0时停止。集合prime_digits是否包含了所有一位质数{2,3,5,7}是否漏掉了2或7验证小范围数据用N100这样的小数据手动计算出所有纯质数2,3,5,7,23,37,53,73与程序输出对比可以快速定位问题。问题3内存占用过大或超时现象当 N 很大如 10^8时程序内存使用激增或运行时间过长。原因与解决内存使用list of bool一个元素占28字节CPythonN10^8需要约2.8GB内存切换为bytearray或array(b)每个元素1字节只需约100MB。时间埃氏筛法 O(N log log N) 对于 10^8 在 PyPy 下也可能需要几秒到十几秒。可以进一步应用“仅筛奇数”优化或将内层循环的步长改为i*2仅标记奇数倍但这会加大代码复杂度。对于本题的 N通常≤10^7优化数组版已足够。5.3 算法扩展与思维提升掌握了埃氏筛法解“纯质数”后我们可以看看这个模板还能解决哪些变种问题以及有哪些更高级的筛法。变种问题举例统计区间内质数个数这是筛法最直接的应用。得到is_prime数组后可以预处理一个前缀和数组prefix_sum其中prefix_sum[i]表示 1 到 i 之间质数的个数。这样查询任意区间[L, R]的质数个数只需要prefix_sum[R] - prefix_sum[L-1]时间复杂度 O(1)。找出所有质因数都是特定集合的数的个数例如“光滑数”相关的问题。可以在筛法过程中不仅标记合数还可以记录或判断其质因数组成。计算每个数的最小质因数LPF或最大质因数GPF在埃氏筛法内层循环标记合数j时如果lpf[j]还未被赋值那么当前的i就是j的最小质因数。这是一个非常有用的预处理。更高效的筛法线性筛欧拉筛埃氏筛法的时间复杂度是 O(N log log N)已经非常优秀。但它有一个小缺点某些合数会被它的多个质因数重复标记例如30会被2、3、5各标记一次。线性筛欧拉筛通过确保每个合数只被它的最小质因数标记一次将时间复杂度优化到了严格的 O(N)。其代码稍复杂核心思想是维护一个质数列表对于每个数i用已知的质数prime[j]去标记合数i * prime[j]并在i % prime[j] 0时跳出循环以保证prime[j]是i * prime[j]的最小质因数。对于“纯质数”问题线性筛的 O(N) 复杂度相比埃氏筛的 O(N log log N) 在理论上更优但当 N 在 10^7 量级时两者的实际运行时间差距很小埃氏筛因其代码简洁更常被使用。当 N 超过 10^8 时线性筛的优势才会逐渐明显。最后一点个人体会解决像“纯质数”这样的问题其价值不在于记住答案而在于完整经历“分析暴力法瓶颈 - 识别适用高级算法筛法 - 实现并优化算法 - 处理边界条件 - 测试验证”的全过程。这种将复杂问题分解、寻找核心矛盾、应用经典模板并加以调整的能力是解决所有工程和算法问题的通用钥匙。下次当你遇到需要统计大量数字某类性质的问题时不妨先想想能不能用“筛”的思想一次性预处理出来这往往就是破题的关键。