从蓝桥杯真题解析纯质数：埃氏筛算法与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这四个一位数质数。如何逐位获取一个整数的各个数字常见的方法有两种转换为字符串将整数p转换为字符串str(p)然后遍历字符串中的每个字符判断其是否在[‘2‘ ‘3‘ ‘5‘ ‘7’]中。这种方法直观易懂。数学取余法通过循环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开始。为什么呢因为对于质数i2*i3*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 # 获取个位数 # 如果某一位数字不是2357中的一个则不是纯质数 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其他偶数不可能为纯质数因为包含非{2357}的数字位 # 我们可以从质数开始遍历或者简单遍历所有奇数加上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不符合{2357}的条件吗5在集合里所以5是纯质数同理2也是纯质数。所以更精确的优化是我们可以只遍历那些每一位都可能是2357的数。但这需要生成所有由这些数字组成的数逻辑稍复杂。在千万量级下直接遍历所有质数的开销是可以接受的质数个数大约为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 边界条件与特殊值处理在编程竞赛中边界条件往往是失分点。对于本题需要特别注意范围包含11不是质数更不是纯质数。数字0如果题目范围从0开始0不是质数。最大值的处理确保循环能正确覆盖到上限limit。单个数字的质数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(f1-{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(f1-{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 竞赛中容易踩的“坑”根据我的经验在解决这类问题时以下几个“坑”最容易让选手失分超时TLE这是最大的坑。直接对每个数使用试除法判断质数在数据量大时必超时。必须使用筛法埃氏筛或欧拉筛进行预处理。内存超限MLE如果使用[True] * (limit 1)且limit很大比如上亿列表会占用几百MB内存。在内存限制严格的比赛中需要考虑使用位数组优化或者分块筛法。概念理解偏差误判“1”1不是质数。误判“0”0不是质数且任何包含0的数都不是纯质数。数字“5”和“2”5和2本身是质数且它们的单一位5和2在合法数字集{2357}内因此它们是纯质数。这一点容易被忽略。循环边界错误在埃氏筛中外层循环for i in range(2, int(limit**0.5)1)这里int(limit**0.5)1必须包含否则如果limit是一个完全平方数其平方根质数可能无法被遍历到。内层标记倍数时for j in range(i*i limit1 i)注意i*i可能一开始就超过limitPython的range会处理这种情况但理解其含义很重要。输出格式错误蓝桥杯通常是填空题或要求输出一个整数。务必确认题目要求是输出“个数”还是“列表”或者求和。我们的函数设计为返回个数和列表适应性较强。6. 举一反三类似问题与扩展掌握了纯质数的解法我们可以轻松应对一系列变体问题。这体现了算法思想的通用性。6.1 变体问题示例绝对质数将一个质数进行数位反转如13反转为31如果反转后的数也是质数则称其为绝对质数。求解时需要同时判断原数和反转数。可截质数从一个质数中从左向右或从右向左连续截取数字得到的每个数都是质数。例如3797从左截取3 37 379 3797都是质数从右截取7 97 797 3797也都是质数。这需要更复杂的递归或迭代检查。按位筛选的扩展如果不是要求每位都是质数而是要求每位满足其他条件如都是偶数、都是奇数、数字之和为质数等只需要修改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 limit1) 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 limit1 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)})这样我们就把质数相关的功能封装起来后续解题时可以直接调用避免重复编写筛法代码既提高了效率也减少了出错的可能。回过头看“纯质数”这个问题就像一个精致的引子它把基础的数论知识和编程技巧串联起来。解决它的过程本质上是在训练我们将复杂问题分解为已知模块质数判断、数字位分离并组合解决的能力。在竞赛和实际开发中这种能力远比记忆某个特定算法更重要。我个人的习惯是每解决一道这样的题都会问自己它的核心考点是什么有哪些变体我封装的工具函数能否复用到其他地方经过这样的思考代码才不会白写能力才能真正沉淀下来。