1. 项目概述从一道国赛真题看算法思维的锤炼最近在复盘蓝桥杯国赛的历年真题时我又把第十二届的“纯质数”这道题拿出来仔细琢磨了一遍。这道题初看平平无奇不就是判断质数吗但当你真正动手去实现并追求一个能在竞赛时间限制内通常是1-2秒处理到20210605题目给定的范围终点的高效解法时就会发现里面门道不少。它绝不仅仅是for循环加取模那么简单而是综合考察了我们对数论基础、算法效率、Python语言特性以及边界情况处理的全面理解。很多朋友在练习时要么超时要么漏数最后可能连“纯质数”的定义都没吃透。今天我就结合自己多次调试和教学的经验把这题的“里子”和“面子”都拆开来讲透不仅给出能AC通过所有测试用例的代码更重点分享如何一步步优化以及过程中那些容易踩坑的细节。这道题适合所有正在备战蓝桥杯Python组或是对算法优化感兴趣的朋友。无论你是刚入门的新手还是有一定基础想查漏补缺的选手相信这篇从实战出发的深度解析都能让你对质数判断和综合编程有新的认识。我们不止步于做出答案更要追求清晰、优雅且高效的解决方案。2. 核心需求与定义拆解到底什么是“纯质数”在动手写代码之前我们必须像审题官一样把题目要求掰开揉碎理解每一个约束条件。这是避免方向性错误的第一步。2.1 题目定义的精确解读题目要求我们找出1到20210605之间所有“纯质数”的个数。那么“纯质数”的定义就成为了核心。根据题目描述它需要同时满足两个条件它本身是一个质数。这是基础。质数的定义是在大于1的自然数中除了1和它本身以外不再有其他因数的数。因此1不是质数。它的每一位都是质数。这是本题的附加条件。我们需要将这个数按十进制每一位拆开检查每一位的数字0-9是否都是质数。这里有一个极其关键的细节也是很多初学者第一个掉进去的坑“每一位都是质数”中的“质数”指的是数字本身0-9是否为质数而不是指该位上的数字作为一个一位数是否是质数虽然对于一位数来说这两者在结果上等价但思考角度不同。2.2 关键数字集合分析基于以上定义我们可以先分析0-9这十个数字中哪些是“质数数字”质数数字2, 3, 5, 7。这四个数字本身是质数。非质数数字0, 1, 4, 6, 8, 9。其中0和1既不是质数也不是合数4, 6, 8, 9是合数。由此我们可以推导出一个非常重要的优化剪枝策略如果一个数包含0,1,4,6,8,9中的任何一个数字那么它一定不是纯质数。我们可以在判断其本身是否为质数之前先进行这一步检查从而提前排除大量显然不合格的数字节省大量不必要的质数判断计算。注意这个剪枝条件非常强大。例如数字23个位是3十位是2都是质数数字因此它有资格进入下一步质数判断。而数字29个位是9非质数数字直接淘汰无需判断29是否为质数。2.3 输入输出与数据范围明确输入本题通常没有输入或者说范围是固定的从1到20210605。输出一个整数即范围内纯质数的个数。数据范围20210605这个上限约等于2e7两千万。这是一个中等偏大的范围。如果我们对每一个数都用最朴素的O(√n)方法去判断质数最坏情况下的计算量会非常大大约2e7 * √(2e7) ≈ 9e10次运算在Python中必然超时。因此算法效率是本题的核心挑战。3. 算法设计与思路演进从暴力到高效面对2e7的数据范围我们不能蛮干。下面我带你走一遍我的思考过程从最直觉的暴力法开始一步步优化到能够稳定AC的算法。3.1 思路一朴素暴力法不可行但必须理解这是最直接的思路也是我们思考的起点遍历i从2到20210605。对于每个i先判断其每一位是否由{2,3,5,7}组成。如果满足条件2再判断i本身是否为质数用2到√i的整数去试除。统计满足以上两个条件的i的个数。复杂度分析判断每一位是O(log i)判断质数是O(√i)。总体复杂度约为O(n √n)对于n2e7不可接受。这是一个必须抛弃的方案但它帮助我们理清了逻辑顺序。3.2 思路二质数判断优化 剪枝我们引入两个关键优化提前剪枝在判断质数之前先检查数字的每一位。如果任何一位是{0,1,4,6,8,9}则直接跳过该数。这能过滤掉大部分数字。质数判断优化偶数除了2一定不是质数可以直接跳过。试除时除数从3开始每次加2只检查奇数直到√i。更进一步的可以只用6k±1形式的数来试除即除2和3外所有质数都符合这个形式。即使这样对于每个需要通过剪枝的数我们仍要进行一次O(√i)的质数判断。在2e7范围内纯质数的数量虽然远小于总数但每个的判断成本依然不低在Python中仍有超时风险不够稳健。3.3 思路三埃拉托斯特尼筛法Sieve of Eratosthenes这是处理大规模范围内质数筛选问题的经典算法也是本题的推荐核心解法。其核心思想不是单独判断每个数而是“批量”找出所有不是质数的数合数剩下的就是质数。算法步骤简述创建一个大小为n1的布尔数组is_prime初始假设所有数都是质数设为True。将is_prime[0]和is_prime[1]标记为False0和1不是质数。从p 2开始遍历到√n如果is_prime[p]是True那么p是一个质数。然后将p的所有倍数从p*p开始到n结束步长为p标记为False它们是合数。完成后所有is_prime[i] True的i就是质数。为什么筛法更优它的时间复杂度大约是O(n log log n)对于n2e7这个复杂度是完全可以接受的。我们只需要运行一次筛法就能得到从1到n所有数的质数真值表。之后判断任意一个数i是否为质数只需要O(1)的时间查询is_prime[i]即可。这完美解决了思路二中每个数都需要重复计算√i次的问题。结合本题的改造 我们不再需要为每个数单独判断质数。流程变为先用筛法生成is_prime数组范围到20210605。遍历i从2到20210605。对每个i先进行“每一位是否为质数数字”的剪枝判断。如果通过剪枝再用O(1)的时间查询is_prime[i]。统计最终数量。这个方案的效率瓶颈在于筛法本身的空间和时间开销以及遍历所有数进行剪枝判断的开销。但整体效率远高于思路二是稳定AC的保障。3.4 思路四深度优化——逆向生成候选数这是一个更巧妙的思路可以进一步减少需要检查的数字数量。既然纯质数的每一位只能是{2,3,5,7}那么我们可以直接生成所有由这些数字组成的数然后再判断它们是否为质数。生成方法例如使用DFS或BFS从一位数开始2,3,5,7。生成两位数在2,3,5,7后面分别追加2,3,5,7得到22,23,25,27,32,33,...直到生成的数超过上限20210605。以此类推生成所有不超过上限的、由{2,3,5,7}组成的数。优势需要检查的数大大减少。在20210605范围内这样的数字数量是有限的4^1 4^2 ... 4^7因为4^8 2e7所以最多7位数总数远小于两千万。然后对这批“候选数”用筛法或优化后的单次判断进行质数检验即可。劣势实现起来比思路三稍复杂需要处理数字的生成和去重。但对于追求极致效率或者上限n变得更大时这个思路的优势会更明显。在本题n2e7的条件下思路三的筛法实现简单且完全够用。最终选择对于蓝桥杯赛场环境思路三筛法剪枝在实现复杂度、可靠性和效率之间取得了最佳平衡是我们接下来实现和详解的重点。4. 核心代码实现与逐行解析接下来我们基于“埃氏筛剪枝”的方案编写完整的Python代码。我会对每一部分进行详细注释并解释关键点。def is_pure_prime(num): 判断一个数是否为纯质数。 1. 检查每一位是否由质数数字(2,3,5,7)组成。 2. 再检查其本身是否为质数通过查表。 # 步骤1: 检查每一位数字 temp num while temp 0: digit temp % 10 # 获取个位数 # 如果个位数不在{2,3,5,7}中直接返回False if digit not in {2, 3, 5, 7}: return False temp // 10 # 去掉个位数 # 步骤2: 每一位都合格再查询质数表 return is_prime[num] def sieve_of_eratosthenes(limit): 埃拉托斯特尼筛法生成一个布尔列表is_prime。 is_prime[i]为True表示i是质数。 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 def main(): limit 20210605 # 1. 生成质数表 is_prime sieve_of_eratosthenes(limit) count 0 # 2. 遍历2到limit的所有数 for num in range(2, limit 1): # 注意从2开始1不是质数 if is_pure_prime(num): count 1 print(count) if __name__ __main__: main()代码关键点解析is_pure_prime函数它首先进行“逐位检查”。这里用了一个while循环和取模%、整除//运算来分解数字的每一位这是处理数字位运算的常用技巧。检查条件digit not in {2, 3, 5, 7}。这里使用集合{}进行成员判断其平均时间复杂度是O(1)比用列表[2,3,5,7]更快。顺序很重要先检查数位再查质数表。因为数位检查很快O(log n)且能过滤掉大部分数避免了不必要的质数表查询。sieve_of_eratosthenes函数is_prime [True] * (limit 1)创建长度为limit1的列表是为了让索引i直接对应数字i方便查询。for i in range(2, int(limit ** 0.5) 1):外层循环只需要到√limit。这是一个关键优化因为如果limit有一个大于√limit的因子那么它必然还有一个小于√limit的因子这个因子肯定已经被之前的循环标记过了。if is_prime[i]:只有i是质数时才需要去标记它的倍数。如果i已经被标记为合数那么它的倍数肯定也被更小的质因数标记过了。for j in range(i * i, limit 1, i):内层循环从i*i开始标记。为什么不是从2*i开始因为对于质数i2*i,3*i, ...,(i-1)*i这些数它们的最小质因数小于i所以在之前遍历到更小的质数时就已经被标记为False了。从i*i开始可以避免重复标记是埃氏筛的标准优化。主函数main首先生成整个范围的质数表。这是一次性的开销。然后遍历从2开始的所有数1不是质数直接跳过调用is_pure_prime判断。最后输出计数。实操心得在Python中对于2e7大小的布尔列表内存占用大约为20MB一个布尔值在Python中实际占用更多但使用array(b)或bytearray可以优化不过本题列表大小可以接受。筛法的运行时间在普通PC上大约1-2秒完全在蓝桥杯的时间限制内。如果担心内存可以考虑使用bytearray来替代列表内存占用会缩小到约20MB/82.5MB。5. 性能优化与进阶探讨虽然上面的代码已经可以AC但追求极致的我们还可以思考更多。这里分享一些更深层次的优化思路和变体帮助你在遇到类似但更复杂的问题时游刃有余。5.1 筛法的内存与时间优化使用bytearray或array(b)Python的list存储布尔值效率不高。bytearray是一个更紧凑的字节数组可以显著减少内存使用有时也能加快访问速度。def sieve_with_bytearray(limit): is_prime bytearray(b\x01) * (limit 1) # 1代表True is_prime[0] is_prime[1] 0 # 0代表False for i in range(2, int(limit**0.5)1): if is_prime[i]: step i start i * i is_prime[start:limit1:step] b\x00 * ((limit - start)//step 1) return is_prime注意这种切片赋值的方式在某些情况下比for循环更快因为它利用了底层C语言的优化。分段筛法当limit极大例如超过1e8无法一次性分配内存时可以将区间分段每次只筛一段。这需要更复杂的实现但能突破内存限制。5.2 纯质数判断的进一步剪枝我们之前的剪枝是“检查每一位是否属于{2,3,5,7}”。但我们可以更早地应用一些数论知识末尾数字剪枝除了2以外所有质数的个位只能是1,3,7,9对于大于5的质数。但我们的纯质数要求每一位都是质数数字{2,3,5,7}所以个位只能是2,3,5,7。这和我们之前的逐位检查是一致的但我们可以优先检查个位因为取模运算很快。数字和剪枝需谨慎一个数能被3整除当且仅当其各位数字之和能被3整除。如果由{2,3,5,7}组成的数其数字之和能被3整除那么这个数本身也能被3整除除了3本身因此不是质数。例如272792222226等。我们可以在生成候选数或检查时加入这个条件提前排除一些明显的合数。但注意这个计算数字和本身也有开销需要权衡。5.3 “逆向生成”法的具体实现作为思路四的实现示例我们可以用DFS来生成所有候选数def generate_candidates(limit): 生成所有不超过limit的、由数字{2,3,5,7}组成的数 candidates [] digits [2, 3, 5, 7] def dfs(current): if current limit: return if current 1: # 1不是质数 candidates.append(current) for d in digits: next_num current * 10 d dfs(next_num) dfs(0) # 从0开始生成 return candidates def main_advanced(): limit 20210605 # 生成候选数数量远小于limit candidates generate_candidates(limit) # 为了快速判断质数我们仍然需要筛法但范围只需要到limit is_prime sieve_of_eratosthenes(limit) # 复用之前的筛法函数 count 0 for num in candidates: if is_prime[num]: count 1 print(count)这种方法生成的candidates数量大约在(4^8 -1)/(4-1) ≈ 21845个左右远小于两千万。然后只需要对这些候选数进行质数判断效率极高。这是本题理论上最优的解法之一。6. 常见错误与调试心得在实现和教学过程中我见过学生们踩过各种各样的坑。这里总结一下帮你避雷。6.1 错误类型与排查表错误现象可能原因解决方案结果比标准答案小1. 漏掉了质数2。2. 遍历范围从1开始错误地将1计入。3. 筛法实现有误错误地将一些质数标记为合数。1. 确认2是否被正确判断2是质数且每一位2是质数数字。2. 遍历应从2开始。3. 检查筛法循环边界和标记逻辑特别是i*i可能溢出在Python中不会但其他语言要注意或步长错误。结果比标准答案大1. 错误地将1计为质数。2. 质数判断函数逻辑错误将合数判为质数如试除边界写错。3. “纯质数”判断逻辑错误例如只判断了本身是质数没判断数位。1. 明确1不是质数。2. 单次质数判断时试除范围应是[2, √n]且需要包含边界。用i*i n作为循环条件更安全。3. 复核is_pure_prime函数确保两步判断都执行。程序运行超时1. 对每个数都使用了O(√n)的质数判断法。2. 筛法实现效率低下如重复标记。3. 在Python中使用低效的容器或循环。1. 换用筛法预处理。2. 优化筛法外层循环到√n内层从i*i开始。3. 使用局部变量、set进行成员判断、避免不必要的函数调用和对象创建。内存占用过大使用list of bool存储过大的质数表。换用bytearray或array(b)。对于极端大的范围考虑分段筛。6.2 调试与测试技巧从小范围开始验证不要一开始就在20210605上跑。先测试1-100或1-1000的结果。你可以手动或写一个简单的暴力程序计算出小范围的正确结果用来验证你的优化算法是否正确。打印中间结果对于小范围测试可以打印出所有找到的纯质数直观检查。例如100以内的纯质数应该有2, 3, 5, 7, 23, 37, 53, 73。检查你的程序是否能正确输出这些数。性能分析使用Python的time模块或cProfile来测量代码不同部分的运行时间找到瓶颈。例如你会发现筛法部分耗时最多而遍历判断部分相对较少。边界条件测试特意测试2最小的质数和纯质数、20210605上限它不是纯质数因为它包含0和6等等我们看一下20210605包含数字0,1,2,6有0和1和6所以肯定不是、以及像7777777全由7组成但它是合数吗这样的特殊数字。6.3 关于“1”的处理再强调这是一个超级高频错误点。1不是质数所以即使1的每一位就是它自己满足质数数字的条件1不是质数数字它也不是纯质数。我们的循环必须从2开始。在“逆向生成”法中dfs生成的第一个数是0然后会生成2,3,5,7,...我们需要在添加候选数时跳过0和1。7. 总结与举一反三通过这道“纯质数”题我们深入实践了以下几个核心技能点这些也是蓝桥杯乃至所有算法竞赛中的通用能力问题分析与定义转化将“纯质数”这个自然语言描述精确转化为“本身是质数”且“每一位属于集合{2,3,5,7}”两个可编程检查的逻辑条件。算法选型与复杂度分析面对2e7的数据范围立刻意识到朴素暴力法不可行进而联想到筛法这一高效预处理工具并理解其O(n log log n)复杂度远优于O(n √n)。优化策略的综合运用剪枝利用“非质数数字”提前淘汰大量候选者这是减少无效计算的关键。预处理空间换时间使用筛法一次性算出所有质数状态使后续每次判断降为O(1)。常数优化在筛法中使用i*i作为起点在判断数位时使用集合in操作。代码实现的严谨性注意循环边界int(limit**0.5)1、起始值从2开始、以及1不是质数这类边界条件。更优解法的探索思维“逆向生成候选数”的思路跳出了“遍历-判断”的定式通过构造解空间来极大缩小搜索范围体现了算法设计中的创造性。这道题可以有很多变体例如“纯合数”每一位都是合数数字4,6,8,9的数并且本身是合数。“幸运质数”本身是质数且各位数字之和也是质数。范围更大如果上限提高到10^9完整的筛法内存可能不够就需要用到“分段筛法”或“米勒-拉宾素性测试”等更高级的算法来判断单个大数是否为质数。最后我个人的一点体会是刷题不能只满足于AC。像这样把一道题吃透搞清楚每一种方法为什么快、为什么慢边界在哪里还能怎么优化比盲目刷十道题都管用。当你再遇到“质数”、“数位”相关的题目时你工具箱里的方法就会非常清晰能够快速组合出最适合的解决方案。这才是备赛和提升编程能力的正确路径。