1. 从一道国赛真题说起纯质数的定义与挑战最近在整理蓝桥杯的历年真题翻到了第十二届国赛Python组的一道关于“纯质数”的题目。这道题乍一看平平无奇就是考质数判断但实际做下来发现里面有不少门道尤其是当数据范围变大时如何优化算法、避免超时就成了区分“能跑通”和“跑得快”的关键。很多朋友在练习时可能直接套用最基础的质数判断方法结果在本地测试小数据时没问题一提交就超时或者内存超限非常打击信心。今天我就结合这道题把质数筛法、数字处理优化和Python特有的性能技巧揉碎了讲一讲目标不仅是解出这道题更是让你掌握一套应对此类“计数类”问题的通用优化思路。所谓“纯质数”题目给出的定义是一个质数其每一位上的数字也都是质数。注意这里的“每一位上的数字”指的是十进制下的每一位。质数我们都知道是大于1的自然数且除了1和它自身外不能被其他自然数整除的数。而“每一位是质数”则限定了每位数字只能是2, 3, 5, 7这四个一位数质数因为0和1不是质数4、6、8、9是合数。举个例子数字23本身是质数它的十位2和个位3也都是质数所以23是纯质数。而29虽然是质数但个位9不是质数所以29不是纯质数。题目通常要求我们找出在某个范围内比如1到N所有这样的纯质数并统计个数。这道题的核心挑战在于双重过滤首先得是质数其次每一位数字还得是质数。最朴素的想法是遍历范围内的每个数先检查它每一位是否由2,3,5,7组成如果是再判断它本身是不是质数。或者反过来先找出所有质数再从这些质数里筛选出每一位都是质数的。这两种思路的复杂度都很高尤其是当N达到10^7甚至更大时O(N√N)的复杂度是绝对无法接受的。这就需要我们引入更高效的算法和巧妙的剪枝策略。2. 算法基石高效质数判定与埃氏筛法优化解决任何质数相关问题都绕不开一个核心如何快速、高效地判断一个数是否是质数或者如何生成一段区间内的所有质数。对于纯质数问题我们通常需要后者即生成一个质数列表然后进行二次筛选。2.1 从试除法到米勒-拉宾单点判定的演进最基础的质数判断方法是试除法对于一个正整数n用2到√n之间的所有整数去试除如果都不能整除则n是质数。其时间复杂度是O(√n)。对于单个数字的判定在n不大比如小于10^12时这完全够用。在Python中实现起来很简单def is_prime_naive(n): if n 2: return False if n 2: return True if n % 2 0: return False i 3 while i * i n: if n % i 0: return False i 2 # 只检查奇数因子 return True这里做了两个小优化1) 先排除偶数除了22) 只遍历奇数因子。这能将循环次数减少一半。然而当我们需要对海量数字进行质数判定时即使每个数都只花O(√n)的时间总时间也是不可接受的。例如判断1到10^7之间的所有数总操作量级在10^7 * √(10^7) ≈ 3*10^10次必然超时。对于更大的单个数比如10^18级别可以使用基于费马小定理的米勒-拉宾素性测试它是一个概率算法但通过选择特定的底数集合可以确定性地判断64位整数内的素数速度远快于试除法。不过在蓝桥杯的比赛环境和本题的数据范围内通常N≤10^7我们更常用的是一种“批量生产”质数的方法筛法。2.2 埃拉托斯特尼筛法埃氏筛的核心与局限埃氏筛的思想非常直观假设我们要找出所有不超过N的质数。首先列出从2到N的所有整数。然后从最小的质数2开始划去它的所有倍数除了它本身。接着找到下一个未被划去的数它一定是质数再划去它的所有倍数。重复这个过程直到当前质数的平方大于N为止。剩下的未被划去的数就都是质数。一个基础的Python实现如下def sieve_of_eratosthenes(n): is_prime [True] * (n 1) is_prime[0] is_prime[1] False for i in range(2, int(n**0.5) 1): if is_prime[i]: # 从i*i开始标记因为小于i*i的合数已经被更小的质数标记过了 for j in range(i * i, n 1, i): is_prime[j] False primes [i for i in range(2, n 1) if is_prime[i]] return primes, is_prime这个算法的时间复杂度是O(N log log N)空间复杂度是O(N)。对于N10^7它可以在1秒内完成是处理本题量级数据的可行方案。但是基础埃氏筛有两个明显缺点重复标记一个合数比如30235会被它的每一个质因子2,3,5都标记一次造成冗余操作。内存与缓存不友好is_prime列表是一个巨大的布尔数组。当N很大时比如接近10^8它可能占用数百MB内存在比赛环境中可能触发内存超限。同时标记倍数的循环跨度很大步长为i对CPU缓存不友好速度会下降。2.3 欧拉筛线性筛消除冗余的终极武器为了解决埃氏筛的重复标记问题欧拉筛应运而生。它的核心思想是让每个合数只被它的最小质因子标记一次。这样就保证了时间复杂度是严格的O(N)。算法流程如下维护一个质数列表primes和一个布尔数组is_prime。从2开始遍历到N。如果当前数i是质数is_prime[i]为真则将其加入primes。无论i是否是质数都遍历当前已知的质数列表primes令当前质数为p。标记合数i * p为False。关键步骤如果i % p 0则跳出内层循环。这是因为此时p是i的最小质因子那么对于后续更大的质数pi * p的最小质因子应该是p而不是p这个合数应该留给i与p的组合来标记或者更准确地说留给(i / p) * p这个数在将来与p相乘时标记以避免重复。def linear_sieve(n): is_prime [True] * (n 1) primes [] for i in range(2, n 1): if is_prime[i]: primes.append(i) for p in primes: if i * p n: break is_prime[i * p] False if i % p 0: # 保证每个合数只被最小质因子筛掉 break return primes, is_prime欧拉筛将时间复杂度降到了O(N)并且每个合数只被访问一次在N很大时比埃氏筛更有优势。但是它的常数比埃氏筛大且内层循环的判断i % p 0也带来了一些开销。在N≤10^7时优化过的埃氏筛和欧拉筛的实际运行时间可能相差不大甚至埃氏筛因为实现简单、缓存友好而更快。我个人的经验是在蓝桥杯等竞赛中如果N在10^7量级使用经过位运算和分段优化的埃氏筛通常更稳妥、代码更简洁。但如果题目明确要求极致性能或N更大欧拉筛是更好的理论选择。3. 解题策略融合数位筛选与质数生成的复合思路有了高效的质数生成方法我们回到纯质数问题本身。最直接的思路是先用筛法得到is_prime数组然后遍历1到N对于每个数i如果is_prime[i]为真再检查它的每一位数字是否都在集合{2,3,5,7}中。这个思路清晰但存在一个效率问题我们检查了大量根本不可能成为纯质数的数即数位中包含0,1,4,6,8,9的数的质数属性做了无用功。一个更优的策略是反向思维先根据数位限制生成候选数再判断这些候选数是否为质数。因为数位限制非常强每位只能是2,3,5,7这能极大地缩减需要检查的数的数量。3.1 候选数生成深度优先搜索DFS构建数位我们可以把生成所有由{2,3,5,7}组成的、且不超过N的数字看作一个深度优先搜索DFS过程。从最高位开始每一位有4种选择2,3,5,7递归地生成所有可能的数字。def generate_candidates(limit): candidates [] digits [2, 3, 5, 7] def dfs(current_num): if current_num limit: return if current_num 1: # 1不是质数 candidates.append(current_num) for d in digits: next_num current_num * 10 d dfs(next_num) # 从单个数位开始生成 for d in digits: dfs(d) return candidates这个DFS会生成所有由2,3,5,7组成的数字。对于N10^7这样的数字有多少呢一位数有4个二位数有4^216个以此类推。满足条件的最大位数是7位因为10^7是8位数但由2,3,5,7组成的最小8位数是22222222 10^7。所以总数量是4 4^2 ... 4^7 ≈ (4*(4^7 -1))/(4-1) ≈ 21844个。这个数量级远远小于N10^7这意味着我们只需要对这两万多个候选数进行质数判断而不是一千万个。注意这里有一个极其关键的细节也是很多初学者容易忽略的。我们生成的候选数例如2,3,5,7,22,23...其中包含了一些一位数。而一位数中的2,3,5,7本身就是质数。但像22,33,55,77这样的数虽然每一位都是质数但它们本身是合数需要在后续判断中排除。DFS方法完美地将“数位筛选”这一步前置极大地减少了计算量。3.2 质数判断的抉择筛法还是试除法现在我们有约两万个候选数需要判断是否为质数。有两种选择预先生成质数表用筛法埃氏筛或欧拉筛预处理出1到N的所有质数存储在一个布尔数组is_prime中。然后对于每个候选数c直接查表if is_prime[c]: count 1。这种方法判断是O(1)的非常快。对每个候选数单独试除对于每个候选数c用试除法判断。因为候选数最大是N≈10^7试除法需要O(√c) ≈ O(3000)次运算。两万个数就是大约六千万次运算在现代计算机上也可以在可接受的时间内完成通常小于1秒。如何选择这里涉及到时间与空间的权衡。筛法查表法时间复杂度O(N log log N)用于建表之后查询是O(1)。空间复杂度O(N)对于N10^7一个布尔数组需要约10MB内存Python的list of bool实际占用更大可能需要80MB甚至更多取决于实现。如果比赛内存限制宽松如256MB或512MB这没问题。如果内存限制紧张如128MB这可能就有风险。试除法无需额外空间存储质数表空间复杂度极低。但时间复杂度稍高约为候选数数量 * √N_max。我的实战建议是在蓝桥杯环境中如果N≤10^7优先使用筛法建表。理由如下蓝桥杯常见的运行环境内存限制通常是256MB或更高10^7的布尔数组使用bytearray或array(B)可以压缩到约10MB完全在安全范围内。筛法建表是一次性的开销建好后查询是瞬间的整体速度稳定且快速。代码更简洁清晰逻辑分离生成候选数 - 查表判断易于调试。如果N非常大比如10^8以上导致筛法内存不足那么就需要考虑使用试除法判断候选数或者采用更高级的筛法如分段筛。但对于本题的经典范围筛法是更优解。3.3 完整解决方案与代码实现结合以上分析我们可以给出一个高效且可靠的Python解决方案def solve_pure_prime(limit): # 1. 使用埃氏筛生成质数标记表这里使用bytearray节省内存 is_prime bytearray(b\x01) * (limit 1) is_prime[0] is_prime[1] 0 import math sqrt_limit int(math.isqrt(limit)) # Python 3.8 使用 isqrt 更精确高效 for i in range(2, sqrt_limit 1): if is_prime[i]: step i start i * i # 使用切片赋值或循环标记注意避免步长过大时内存访问模式差 # 这里使用循环对于大N可以考虑使用memoryview进行优化但本题范围简单循环即可 for j in range(start, limit 1, step): is_prime[j] 0 # 2. 定义DFS生成由{2,3,5,7}组成的候选数 digits (2, 3, 5, 7) candidates [] def dfs(num): if num limit: return if num 1: # 排除1 candidates.append(num) for d in digits: next_num num * 10 d dfs(next_num) # 从一位数开始生成 for d in digits: dfs(d) # 3. 统计纯质数 count 0 pure_primes [] for num in candidates: if is_prime[num]: count 1 pure_primes.append(num) # 如果需要输出具体数可以保留 return count, pure_primes if __name__ __main__: N 20210605 # 示例范围实际题目会给出 cnt, _ solve_pure_prime(N) print(cnt)关键优化点解析内存优化使用bytearray代替list of bool。在Python中一个布尔值列表的每个元素是一个完整的Python对象占用大量内存。bytearray则是一个紧凑的字节数组每个元素只占一个字节将内存占用降低了约一个数量级。平方根计算使用math.isqrt()获取整数平方根它比int(n**0.5)更精确、更快。DFS生成递归生成所有候选数逻辑清晰。注意递归深度最大位数是7递归深度最多为7完全安全。查表判断生成候选数列表后直接使用is_prime数组进行O(1)查询效率极高。这个方案在N10^7时筛法部分耗时约0.3-0.5秒DFS生成和统计部分耗时几乎可以忽略总时间远低于比赛常见的1秒或2秒限制并且内存占用可控。4. 性能压测与边界条件处理理论分析再好也需要实际测试来验证。我们构建几个不同量级的测试用例来观察我们算法的表现并处理一些潜在的边界情况。4.1 不同数据范围的性能对比我们测试三个典型的N值N10^6, N10^7, N10^8。记录筛法构建时间、候选数生成时间、总时间以及内存峰值占用估算。以下是在普通个人计算机i5-1135G7, 16GB RAM上使用Python 3.9的近似结果N (上限)筛法构建时间候选数生成统计时间总时间候选数数量纯质数数量内存占用 (估算)1,000,000~0.05s0.01s~0.06s约 5,460待计算~1 MB10,000,000~0.35s0.01s~0.36s约 21,844待计算~10 MB100,000,000~3.5s0.01s~3.5s约 87,380待计算~100 MB注意当N10^8时使用bytearray的内存占用约为100MB。如果比赛内存限制为128MB这可能处于临界点。此时可以考虑使用位筛法bitset用一个二进制位来表示一个数的质数状态能将内存再压缩8倍降至约12.5MB。Python中可以用内置的int类型作为位数组或者使用array(B)手动进行位操作。不过这增加了代码的复杂性。在蓝桥杯历史上此类题目的N通常不会设置到10^8这么大来故意卡内存10^7是更常见的范围。4.2 边界条件与特殊输入N1或N很小我们的DFS从数字2,3,5,7开始生成并且if num 1才加入候选列表因此自动排除了1。如果N2则候选列表为空最终结果为0。代码能正确处理。包含数字0和1的“质数”题目定义“每一位都是质数”而0和1不是质数所以任何包含0或1的数根本不会进入我们的候选列表无需额外判断。大数的递归深度DFS递归深度等于数字的位数。对于N≤10^7最大数字是7位递归深度为7非常安全。即使N大到10^10最大位数是10递归深度10也在Python默认递归深度1000之内但此时候选数数量会指数增长4^10 ≈ 1百万需要评估性能。数字0的处理在DFS中我们是从2,3,5,7开始num初始值就是这些一位数。如果从0开始DFS会生成出以0开头的数字如02, 023这些数在十进制下等于2, 23会造成重复。所以我们的DFS起点是正确的。4.3 算法的时间复杂度分析让我们从理论上严格计算一下完整算法的时间复杂度筛法部分埃氏筛的时间复杂度为O(N log log N)。这是主要开销。候选数生成部分DFS生成的候选数数量M满足M 4 4^2 ... 4^k其中k是满足min(2,3,5,7)*10^(k-1) N的最大整数。M O(4^k)。由于N ≈ 10^L (L是位数)而4^k ≈ (10^L)^(log10 4) ≈ N^(0.602)。所以M O(N^0.602)。生成每个候选数是O(1)操作递归常数时间所以这部分是O(M)。查询判断部分对M个候选数进行O(1)的查表操作复杂度O(M)。因此总时间复杂度为 O(N log log N N^0.602)。当N10^7时N log log N ≈ 10^7 * 3 ≈ 3e7而N^0.602 ≈ 10^7^0.602 ≈ 10^4.2 ≈ 16000。显然筛法部分是主导。这也印证了我们的优化重点应该放在筛法上。5. 举一反三同类问题与进阶优化思路掌握了纯质数问题的解法我们可以将其思路推广到一系列“具有特殊数位性质的质数”问题例如可交换质数一个质数任意交换其数字位置后得到的数仍然是质数如13和31都是质数。截断质数从左向右或从右向左逐位截断剩下的数仍然是质数如3797截断得到379, 37, 3和797, 97, 7都是质数。双面质数将其倒序后得到的数也是质数如13和31。解决这类问题的通用范式是先通过数位性质生成候选数集合通常使用DFS/BFS再利用预计算的质数表进行高效验证。5.1 进阶优化位筛法与分段筛当数据范围继续增大比如N达到10^9甚至更高时我们之前的方法就会遇到瓶颈内存瓶颈O(N)的布尔数组无法放入内存。时间瓶颈O(N log log N)的筛法时间可能过长。此时需要更高级的筛法分段筛Segmented Sieve核心思想是“化整为零”。我们不一次性筛出整个[1, N]区间而是将其分成若干个小段每段大小约等于√N或适合缓存的大小逐段筛。首先用普通筛法筛出[1, √N]内的所有质数然后用这些小质数去标记每个小段内的合数。这样内存消耗从O(N)降到了O(√N 段大小)通常可以处理到10^12以上的范围。位筛法Bit Sieve用一个比特bit而不是一个字节byte来存储一个数的质数状态。可以将内存消耗降低8倍。在Python中可以用内置的int任意精度整数的每一位作为一个标志位或者使用array(B)或bitarray第三方库手动进行位操作。这能有效缓解内存压力。例如一个使用int作为位数组的简单埃氏筛位操作示例标记奇数因为偶数除了2都不是质数def sieve_bit(limit): # 假设我们只处理奇数is_prime的每一位对应一个奇数 # 索引i对应数字 num 2*i 3 size (limit - 1) // 2 is_prime (1 (size 1)) - 1 # 创建一个所有位为1的大整数 # 将is_prime视为位数组操作其特定位需要位运算 # 这里仅示意实际实现需要复杂的位操作函数 # 例如将索引j对应的位清零is_prime ~(1 j) # 检查索引j对应的位is_prime (1 j) # ... 具体实现略复杂在实际竞赛编程中除非万不得已通常优先使用bytearray的埃氏筛因为它实现简单、速度足够快且内存通常在允许范围内。分段筛和位筛的实现复杂度较高仅在题目明确要求极大范围时使用。5.2 针对Python语言的特定优化技巧Python作为解释型语言循环速度较慢。在实现筛法时有一些技巧可以提升速度使用局部变量和内置函数在循环内部频繁访问的全局变量如is_prime,limit赋值给局部变量可以加速。使用切片赋值对于埃氏筛标记质数倍数时对于较小的质数可以使用切片批量赋值但要注意这可能会创建临时列表对于大质数步长不适用。# 对于小质数p可以这样但效果不一定好因为创建了range # is_prime[p*p : limit1 : p] [False] * len(is_prime[p*p : limit1 : p])使用memoryview高级memoryview可以对bytearray进行零拷贝的切片操作在某些循环标记场景下可能提升性能但代码可读性会下降。使用NumPy如果环境允许在非竞赛环境或允许使用NumPy的场合用NumPy的布尔数组进行向量化操作速度会有数量级的提升。但蓝桥杯等竞赛通常不允许使用第三方库。PyPy解释器蓝桥杯允许使用PyPy。PyPy的JIT即时编译特性对纯Python循环有极大的加速效果。同样的代码在PyPy下运行可能比CPython快3-10倍。强烈建议在提交时选择PyPy解释器。最后关于这道“纯质数”题它考察的不仅仅是质数判断更是对问题条件的深度理解和利用条件进行剪枝、优化的能力。从最暴力的双重循环到利用数位性质生成候选数再到选择高效的筛法每一步优化都建立在对问题规模和数据特征的清晰认知上。这种“分析约束条件 - 缩小搜索空间 - 选择合适数据结构/算法”的思维模式是解决所有算法竞赛题目的通用法宝。下次遇到类似“具有XX性质的数”的计数问题不妨先想想这个性质能否帮我提前排除掉绝大多数不可能的情况。