1. 项目概述从蓝桥杯真题到算法实战最近在复盘一些经典的算法竞赛题目第十二届蓝桥杯的“纯质数”问题让我印象挺深。这题乍一看就是个质数筛选但“纯质数”这个条件一加直接把难度和趣味性都提上来了。它不只是考你会不会写埃拉托斯特尼筛法更考验你对数位操作、边界条件以及算法效率之间平衡的理解。很多朋友在初次接触时要么是暴力求解超时要么是筛选逻辑写漏了条件。今天我就结合这道真题把纯质数的来龙去脉、高效的Python实现方案以及我调试过程中踩过的那些坑系统地梳理一遍。无论你是正在备赛蓝桥杯的学生还是想巩固Python与数论基础的开发者这篇内容都能给你提供一条清晰的、可复现的解决路径。所谓“纯质数”题目中定义是其本身是质数且它的每一位数字也都是质数。注意这里的“每一位数字”指的是十进制下的每一位。质数我们都知道是大于1的自然数且只能被1和自身整除。而数字0-9中属于质数的只有2, 3, 5, 7。所以一个纯质数比如23它本身是质数且十位上的2和个位上的3都是质数。相反13虽然本身是质数但十位上的1不是质数所以它不是纯质数。题目通常要求在一定范围内比如1到20210605找出所有这样的数。这立刻排除了所有包含0,1,4,6,8,9这些非质数数字的数大大缩小了搜索范围但也对筛选策略提出了要求。2. 解题核心思路与算法选型面对这样一个问题最直接的思路就是暴力枚举遍历范围内每一个数先检查它的每一位是否都是2,3,5,7然后再检查它本身是不是质数。但范围一旦大到千万级别如20210605这种O(n√n)的复杂度是绝对无法接受的在竞赛中必然超时。因此我们必须采用更聪明的策略核心思路是先根据数位条件预筛选再对候选集进行质数判断。2.1 思路一基于数位生成的深度优先搜索DFS既然纯质数的每一位只能是2,3,5,7那么我们可以直接生成所有由这些数字组成的数然后再判断其是否为质数。这是一个非常高效的思路因为它直接从源头避免了大量无效的枚举。生成数字可以通过深度优先搜索DFS或迭代来实现。例如我们要生成所有1到N之间的、由{2,3,5,7}构成的数字。DFS函数可以设计为接受一个当前数字num作为参数如果num在范围内且大于1就将其加入候选列表。然后尝试在num的末尾追加2,3,5,7形成新的数字num*10 digit并递归调用。这里需要注意数字不能以0开头但我们用的集合里没有0所以没问题。同时要控制递归深度当新生成的数字超过范围N时就停止该分支的搜索。这种方法的时间复杂度主要取决于范围内由{2,3,5,7}组成的数字的数量这比遍历所有数字要少得多。生成完候选数字后我们再用一个高效的质数判断函数去过滤就能得到最终结果。2.2 思路二埃拉托斯特尼筛法结合数位检查另一种经典思路是使用埃拉托斯特尼筛法简称埃氏筛预先筛出范围内所有的质数然后遍历这些质数检查其每一位是否都是质数。埃氏筛的原理是从2开始将每个质数的所有倍数标记为合数。实现时我们创建一个大小为N1的布尔数组is_prime初始假设所有数都是质数True。然后从2遍历到√N如果is_prime[i]为True则将i的所有倍数从i*i开始标记为False。筛完之后数组中为True的下标就是质数。得到质数列表后我们再遍历它们。对于每个质数p将其转换为字符串遍历每一个字符如果字符不在集合{‘2’ ‘3’ ‘5’ ‘7’}中则淘汰。全部字符都符合的就是纯质数。这种方法的好处是质数判断是批量的、高效的。缺点是需要O(N)的内存空间对于大的N可能压力大并且我们仍然遍历了所有质数来进行数位检查而很多质数可能因为包含非质数数位在第一步就被淘汰了这部分遍历存在些许浪费。但对于本题的规模2千万在现代计算机上是可以接受的。2.3 方案对比与最终选择我们来对比一下DFS生成单点质数判断空间占用小只生成相关数字循环次数极少。但每个候选数都需要进行一次质数判断如果质数判断写得不够优化比如直接试除到√n对于大数可能稍慢。不过我们可以用Miller-Rabin等快速素性测试来优化或者利用埃氏筛的结果进行O(1)查询。埃氏筛数位过滤质数判断是O(1)的但需要额外内存且遍历了所有质数。对于蓝桥杯这道题范围是确定的20210605。我更喜欢第一种思路DFS生成因为它更贴合“纯质数”的定义逻辑清晰且生成的候选数非常少后续即使对每个数进行试除判断总计算量也远小于遍历整个范围。更重要的是这种思路体现了算法竞赛中“利用条件缩小搜索空间”的核心思想。因此下文将主要围绕DFS生成结合质数判断的方案进行详细实现。注意在竞赛中务必先仔细阅读数据范围。如果范围巨大例如10^9埃氏筛的内存可能吃不消DFS生成也可能因为数字太多而变慢这时就需要更数位DP等更高级的方法。但针对本题DFS生成完全够用且优雅。3. 代码实现与逐行解析接下来我们动手实现基于DFS生成方案的Python代码。我会将代码分成几个函数模块并详细解释每一部分的作用和细节。3.1 模块一高效的质数判断函数尽管候选数不多但一个高效的质数判断函数仍是基础。对于大于1的自然数n最常用的方法是试除法检查从2到√n之间的整数是否能整除n。def is_prime(n: int) - bool: 判断一个大于1的整数是否为质数。 使用试除法优化边界和步长。 if n 2: return False if n 2 or n 3: return True if n % 2 0 or n % 3 0: # 排除偶数和非2的倍数 return False # 检查从5开始6k±1形式的数 i 5 while i * i n: if n % i 0 or n % (i 2) 0: return False i 6 return True代码解析与优化点基础边界处理n 2直接返回False因为质数定义要求大于1。2和3是特殊的质数直接返回True。快速排除偶数所有偶数除了2都不是质数。n % 2 0快速排除了一半的数字。6k±1优化这是试除法的一个经典优化。所有大于3的质数都可以表示为6k±1的形式即除以6余数为1或5。因此我们只需要用6k±1的数去试除即可。循环从i5开始检查i即6k-1和i2即6k1是否能整除n。每次循环i增加6。这比逐个检查从5到√n的所有奇数步长为2还要快一些。循环终止条件i * i n等价于i sqrt(n)但避免了计算平方根的开销。这个函数对于本题范围内的数最大两千多万速度非常快。3.2 模块二深度优先搜索生成候选数现在实现DFS函数用于生成所有不超过上限limit、且每一位都是2,3,5,7的数字。def dfs_generate(limit: int, current: int, prime_digits: set, result: list): 深度优先搜索生成由质数数位组成的数字。 :param limit: 上限值 :param current: 当前生成的数字 :param prime_digits: 质数数位集合 {2,3,5,7} :param result: 存储结果的列表 if current limit: return if current 1: # 题目要求质数大于1所以生成的数字至少为2 result.append(current) for digit in prime_digits: new_num current * 10 digit # 如果new_num为0说明current是0且digit是0但我们的digit集合没有0所以不会。 # 为了防止无限递归当new_num为0时也不继续但这里不会发生。 if new_num 0: continue dfs_generate(limit, new_num, prime_digits, result) def generate_candidates(limit: int) - list: 生成所有不超过limit的、每一位都是质数的数字。 prime_digits {2, 3, 5, 7} candidates [] # 注意我们从0开始DFS但会跳过0和1因为current1才加入 # 也可以直接从2,3,5,7开始分别DFS逻辑更清晰。 for start_digit in prime_digits: dfs_generate(limit, start_digit, prime_digits, candidates) # 因为DFS过程中可能生成重复的数字例如从2开始和从23开始...实际上不会重复因为路径唯一 # 但为了保险可以排序去重。不过本题的生成逻辑不会产生重复。 candidates.sort() return candidates代码解析与关键点DFS递归函数dfs_generate是核心。参数current代表当前路径构成的数字。如果current超过上限limit则终止该分支剪枝。如果current大于1则它是一个有效的候选数因为质数必须大于1加入结果列表。递归扩展然后遍历每一个质数数位digit将其附加到current的末尾形成新的数字new_num current * 10 digit并以new_num为新的当前值进行递归。入口点在generate_candidates函数中我们分别以2,3,5,7作为起始数字进行DFS。注意不能从0或1开始因为这样生成的数字会包含前导0实际上我们的digit集合没有0所以从0开始只会生成0而0会被current1条件过滤掉但逻辑上不清晰。直接从质数数位本身开始更直观。去重与排序理论上这种生成方式不会产生重复数字因为每个数字由唯一的数位序列构成。但为了结果整洁我们进行排序。排序不是必须的但有利于后续查看和验证。3.3 模块三主流程与结果整合最后我们将上述模块组合起来并针对题目要求的上限进行计算。def find_pure_primes(limit: int) - list: 找出所有不超过limit的纯质数。 # 1. 生成所有由质数数位组成的候选数字 candidates generate_candidates(limit) print(f生成的候选数字数量{len(candidates)}) # 2. 筛选出其中的质数 pure_primes [] for num in candidates: if is_prime(num): pure_primes.append(num) return pure_primes if __name__ __main__: # 第十二届蓝桥杯真题上限 upper_limit 20210605 pure_primes_list find_pure_primes(upper_limit) print(f在1到{upper_limit}范围内纯质数的个数为{len(pure_primes_list)}) print(它们分别是) # 每行打印10个方便查看 for i in range(0, len(pure_primes_list), 10): print(pure_primes_list[i:i10])运行流程说明find_pure_primes是主函数。它首先调用generate_candidates生成所有可能的“数位纯”的数字。打印生成的候选数数量这能让我们直观感受到筛选条件带来的优化效果相比两千万这个数量级会小很多。遍历每一个候选数用is_prime函数判断其是否为质数。如果是则加入最终结果列表pure_primes。在主程序中设置上限为20210605调用函数并打印结果包括个数和具体列表。3.4 完整可运行代码将上述所有模块整合得到完整的解决方案def is_prime(n: int) - bool: if n 2: return False if n 2 or n 3: return True if n % 2 0 or n % 3 0: return False i 5 while i * i n: if n % i 0 or n % (i 2) 0: return False i 6 return True def dfs_generate(limit: int, current: int, prime_digits: set, result: list): if current limit: return if current 1: result.append(current) for digit in prime_digits: new_num current * 10 digit if new_num 0: continue dfs_generate(limit, new_num, prime_digits, result) def generate_candidates(limit: int) - list: prime_digits {2, 3, 5, 7} candidates [] for start_digit in prime_digits: dfs_generate(limit, start_digit, prime_digits, candidates) candidates.sort() return candidates def find_pure_primes(limit: int) - list: candidates generate_candidates(limit) print(f生成的候选数字数量{len(candidates)}) pure_primes [] for num in candidates: if is_prime(num): pure_primes.append(num) return pure_primes if __name__ __main__: upper_limit 20210605 result find_pure_primes(upper_limit) print(f在1到{upper_limit}范围内纯质数的个数为{len(result)}) print(它们分别是) for i in range(0, len(result), 10): print(result[i:i10])执行这段代码你会先看到类似“生成的候选数字数量XXX”的输出这个数字远小于上限值。然后程序会输出纯质数的总数和列表。根据计算在1到20210605范围内纯质数共有1903个。4. 算法优化与扩展思考上面的方案已经能高效解决问题。但我们可以进一步思考在更极端的情况下或从学习角度还有哪些优化和扩展方向4.1 优化一预计算质数表进行O(1)查询在我们当前的方案中对于每个候选数大约有几万个我们都调用了一次is_prime函数进行试除。虽然单次很快但累计调用几万次试除法中的循环和乘法i*i仍有开销。一个优化策略是先用埃拉托斯特尼筛法预计算出从1到上限limit的所有质数布尔表。然后在判断候选数时直接查表即可时间复杂度是O(1)。def sieve_of_eratosthenes(limit: int): 返回一个布尔列表 is_prime is_prime[i] 为 True 表示 i 是质数。 is_prime [True] * (limit 1) is_prime[0:2] [False, False] # 0和1不是质数 for i in range(2, int(limit**0.5) 1): if is_prime[i]: # 从 i*i 开始标记因为更小的倍数已经被之前的质数标记过了 for j in range(i * i, limit 1, i): is_prime[j] False return is_prime # 在主函数中 def find_pure_primes_optimized(limit: int) - list: is_prime_table sieve_of_eratosthenes(limit) # 预计算质数表 candidates generate_candidates(limit) pure_primes [num for num in candidates if is_prime_table[num]] return pure_primes权衡这种方法将质数判断的耗时转移到了初始化质数表上。埃氏筛的时间复杂度接近O(n log log n)对于limit20210605这个预处理是很快的并且只需要做一次。之后数万次查询都是O(1)。但它的缺点是消耗了O(n)的内存大约20MB布尔数组在内存受限的环境如某些嵌入式竞赛环境可能不适用。而原来的试除法是O(√n)时间复杂度但不需要额外内存。在实际比赛中如果题目内存限制宽松用查表法通常更稳妥、更快。4.2 优化二迭代代替递归生成候选数DFS递归虽然清晰但Python的递归深度有限默认约1000层且递归函数调用有一定开销。对于本题生成的数字最大是8位数20210605递归深度最多为8完全安全。但作为一种编程实践我们可以用迭代队列或栈来实现同样的生成逻辑避免递归的潜在风险。from collections import deque def generate_candidates_iterative(limit: int) - list: prime_digits [2, 3, 5, 7] candidates [] queue deque(prime_digits) # 初始队列放入一位数 while queue: num queue.popleft() if num limit: continue if num 1: candidates.append(num) for digit in prime_digits: new_num num * 10 digit if new_num limit: queue.append(new_num) candidates.sort() return candidates这里使用了队列BFS的思想其实用栈DFS也一样。迭代实现没有递归深度限制逻辑同样清晰。4.3 扩展不同进制下的“纯质数”原题是基于十进制的。我们可以思考一个扩展问题在k进制下如何定义和寻找“纯质数”例如在二进制下数位只能是0和1但质数数位该如何定义通常我们可以定义在k进制下一个“纯质数”是其本身是质数且其每一位数字所代表的十进制值也是质数。那么我们需要先确定在0到k-1的数字中哪些是质数。然后生成算法和判断逻辑可以完全复用只需修改prime_digits集合和数位提取方式使用除k取余法。这可以作为一道很好的扩展练习题帮助你深入理解数位和进制的概念。5. 常见问题与调试心得在实现和调试这个问题的过程中我遇到并总结了一些典型问题这里分享给大家希望能帮你避坑。5.1 问题一结果漏数或多出1症状最终得到的纯质数列表里可能漏掉了像2,3,5,7这样的单个质数或者多出了数字1。根因与解决漏掉单个质数在DFS生成函数中起始条件设置不当。如果我们从current0开始递归那么第一层current0时current1条件为假所以2,3,5,7不会在第一次递归中被加入。它们是在下一层递归中作为new_num被生成并加入的。这没问题。但更清晰的写法是像我们优化后的那样直接以[2,3,5,7]作为起点开始DFS确保它们被包含。多出数字11不是质数。如果在生成候选数时将current1也加入了列表或者质数判断函数is_prime没有正确处理n1的情况就会导致错误。务必确保is_prime(1)返回False并且在生成候选数时条件为if current 1。检查清单质数判断函数是否正确处理了n2的情况候选数生成逻辑是否排除了1单数字质数2,3,5,7是否在最终结果中5.2 问题二递归深度溢出或性能不佳症状程序运行报错“RecursionError: maximum recursion depth exceeded”或者对于大的上限值运行非常慢。根因与解决递归深度溢出如果上限值非常大生成的数字位数很多递归深度可能超过Python默认限制约1000。对于本题上限是8位数深度最多为8安全。但如果上限是10^12递归深度可能达到12仍然安全。不过为了代码的健壮性对于不确定深度的场景建议改用迭代法如队列生成候选数。性能不佳质数判断效率低如果使用最原始的试除法从2试到n-1对于大数会极慢。务必使用优化后的试除法如6k±1优化或预计算的质数表。生成候选数过多确认你的生成逻辑是否正确剪枝。if current limit: return这一行至关重要它能及时终止超出范围的分支避免生成无数不必要的数字。重复计算确保质数判断函数或质数表没有被重复创建。质数表应该只创建一次。调试技巧在DFS函数开头打印current观察生成过程看是否有异常大的数字或无限递归。使用cProfile或time模块对代码进行性能分析找出耗时最长的函数。5.3 问题三数位检查逻辑错误症状程序将一些明显不是纯质数的数如13, 19也包含了进来。根因与解决检查了错误的数位集合确保你用于检查的质数数位集合是{2, 3, 5, 7}而不是{1, 2, 3, 5, 7}或{2, 3, 5, 7, 11}等。1不是质数。数位提取方式错误在埃氏筛方案中如果你先筛出质数再检查数位要确保数位提取是正确的。例如对于质数p13转换为字符串是’13’遍历字符得到’1’和’3’。’1’不在集合中应被淘汰。常见的错误是直接对整数进行模10运算但忽略了检查顺序或处理0的情况。使用字符串转换通常更不易出错。验证方法编写几个简单的测试用例如assert is_pure_prime(23) True # 2和3是质数23是质数 assert is_pure_prime(13) False # 1不是质数 assert is_pure_prime(41) False # 4不是质数 assert is_pure_prime(2) True # 边界情况5.4 问题四对大数运行结果存疑症状对于非常大的上限例如10^9程序运行时间过长或内存占用过高且无法验证结果是否正确。根因与解决算法复杂度对于10^9这样的范围埃氏筛需要约1GB内存布尔数组可能不可行。DFS生成的候选数数量也会增长但相比总数仍然少很多。主要瓶颈在于对大数的质数判断。验证策略小范围验证先用你的程序计算一个小的、容易手动验证的范围比如1-100核对结果。交叉验证尝试用另一种思路比如先埃氏筛再过滤计算同一个稍大的范围比如1-10000看结果是否一致。利用已知结论纯质数是一个已知的整数数列OEIS中的A019546。你可以查找这个数列的前若干项与你程序在小范围的计算结果进行比对。性能估算对于超大范围可能需要更高级的算法如数位DP结合米勒-拉宾素性测试。但在竞赛中通常会给出合理的范围确保常规优化算法能在规定时间和内存内完成。我的心得在算法竞赛中正确性永远是第一位的。在追求效率的同时一定要通过小数据、边界案例和逻辑推理来反复验证程序的正确性。对于纯质数问题牢牢抓住“数位集合{2,3,5,7}”和“质数定义”这两个基本点就能构建出正确的筛选逻辑。效率优化则是锦上添花需要在时间、空间和代码复杂度之间做出权衡。这道题是一个很好的例子它告诉我们充分利用题目条件进行剪枝往往比一味追求高级算法更有效。