1. 从一道真题看算法竞赛中的“纯质数”问题最近在整理蓝桥杯国赛的历年真题时十二届国赛的这道“纯质数”题让我印象很深。它不像动态规划或者图论那样有固定的解题模板更像是一个结合了数论基础、编程技巧和细心程度的综合考察。题目本身描述很简洁如果一个质数素数的每一位都是质数即2, 3, 5, 7那么这个质数被称为“纯质数”。例如2, 3, 5, 7, 23, 37都是纯质数而13不是因为1不是质数29也不是因为9不是质数。题目通常会要求我们在一个给定的范围内比如1到20210605找出所有纯质数或者计算它们的个数。这道题之所以值得拿出来单独讲是因为它完美地体现了算法竞赛中“看起来简单做起来坑多”的一类问题。新手可能会觉得不就是先判断质数再判断每一位的数字嘛两层循环搞定。但实际动手你就会遇到效率问题、边界条件、以及“1”这个特殊数字的处理等细节。很多人在考场上因为时间紧张或者考虑不周很容易在这里丢分。今天我就结合这道真题把“纯质数”问题的来龙去脉、高效解法、以及我踩过的那些坑给大家掰开揉碎了讲清楚。无论你是正在备赛蓝桥杯还是想巩固Python编程和基础算法这篇文章都能给你带来直接的帮助。2. “纯质数”问题的核心定义拆解与算法设计思路要解决这个问题我们首先得把题目要求理解透彻。“纯质数”这个复合条件可以拆解成两个独立的、且必须同时满足的子条件条件A该数本身是一个质数。条件B该数的每一位数字十进制表示下都是质数。这里的“每一位数字是质数”指的是数字0-9中只有2, 3, 5, 7这四个一位数质数是合法的。这意味着一个合法的纯质数其十进制表示中不能出现0, 1, 4, 6, 8, 9这些数字。基于这个拆解最直观的暴力解法思路就出来了遍历范围内的每一个数先检查条件B数位是否全为2,3,5,7如果满足再检查条件A是否为质数。这个思路完全正确但效率是我们要考虑的首要问题。如果题目范围很大比如到10^7甚至更大我们需要更精细的设计。一个关键的优化洞察在于条件B数位检查的计算代价远低于条件A质数判断。检查一个数的每一位数字时间复杂度是O(log n)而判断一个数n是否为质数最朴素的试除法复杂度是O(√n)。因此我们应该把代价低的检查放在前面。对于遍历到的每个数先快速判断其数位是否合法如果不合法就直接跳过避免进行昂贵的质数判断。这个顺序调整能带来显著的性能提升。接下来我们深入这两个条件的实现细节。2.1 质数判断从试除法到埃氏筛的抉择质数判断是编程中的经典问题。对于“纯质数”问题我们需要根据数据范围来选择方法。1. 试除法 (Trial Division)这是最基础的方法。对于一个正整数n如果它是合数则必定有一个不大于√n的质因子。因此我们只需要用2到√n之间的所有整数去试除n即可。def is_prime_trial(n): if n 2: return False # 单独处理2 if n 2: return True # 偶数除了2都不是质数 if n % 2 0: return False # 从3开始到sqrt(n)步长为2只检查奇数 i 3 while i * i n: if n % i 0: return False i 2 return True为什么步长设为2因为我们已经排除了所有偶数除了2所以只需要检查奇数因子即可这能减少一半的循环次数。在本题常见的国赛数据范围如n最大为2*10^7内对单个数字使用优化的试除法是完全可以接受的尤其是当我们已经用条件B过滤掉了大部分数字后。2. 埃拉托斯特尼筛法 (Sieve of Eratosthenes)如果题目要求我们找出某一范围内所有的纯质数或者需要非常频繁地判断多个数是否为质数那么预处理一个质数布尔表筛法会是更优的选择。埃氏筛的核心思想是从2开始将每个质数的倍数标记为合数。def sieve_of_eratosthenes(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]: # 从i*i开始标记因为i*(i-1)等已被更小的质数标记过 for j in range(i * i, limit 1, i): is_prime[j] False return is_prime使用场景分析如果我们需要判断从1到N之间哪些是纯质数那么可以先用筛法得到长度为N1的is_prime列表。之后对于任意数x判断is_prime[x]是否为True即可时间复杂度是O(1)。虽然筛法预处理的时间复杂度是O(N log log N)空间复杂度是O(N)但后续的查询效率极高。在蓝桥杯竞赛环境中如果N在10^7量级使用筛法通常是安全且高效的。踩坑点使用筛法时务必注意limit的取值。如果题目问的是“不超过N的纯质数个数”那么limit就是N。同时初始化列表和标记循环的边界要仔细处理避免索引越界。2.2 数位检查高效提取与集合判断判断一个数的每一位是否都由{2,3,5,7}组成方法有很多。方法一整数逐位分解通过循环取模和整除运算依次得到每一位数字。def is_pure_digit(num): valid_digits {2, 3, 5, 7} while num 0: digit num % 10 # 获取个位数 if digit not in valid_digits: return False num // 10 # 去掉个位数 return True注意特殊情况当num为0时这个循环不会执行直接返回True。但0不是质数会在质数判断阶段被过滤掉所以不影响最终结果。不过更严谨的做法可以在函数开始判断if num 0: return False。方法二字符串转换将数字转换为字符串然后遍历每个字符。def is_pure_digit_str(num): valid_chars set(2357) return all(ch in valid_chars for ch in str(num))这种方法代码更简洁但效率略低于整数运算因为涉及字符串的创建和遍历。在竞赛中对于大数据量整数运算通常更快。不过在Python中对于本题的规模两种方法的差异可能并不明显选择你更熟悉、更不易出错的方式即可。一个重要的优化我们可以利用“纯质数”的数位特性直接生成候选数而不是遍历所有数再过滤。因为每一位只能是2,3,5,7我们可以用深度优先搜索(DFS)或队列(BFS)来生成所有由这些数字组成的数然后再判断它们是否为质数。这种方法能极大地减少需要检查的数的数量。例如在1到10000的范围内由{2,3,5,7}组成的数只有4^1 4^2 4^3 4^4 340个远小于10000。我们会在后续章节详细讨论这种“生成法”。3. 实战代码两种主流解法的实现与对比理解了核心思路后我们来看两种具体的代码实现。我将以蓝桥杯第十二届国赛真题的典型要求为例计算1到20210605之间有多少个纯质数。这个范围约2*10^7对于个人电脑的普通算法在时间限制内是可行的。3.1 解法一遍历过滤法朴素但清晰这是最直接的思路遍历范围内每个数先用数位检查过滤再判断质数。def count_pure_primes_naive(limit): def is_prime(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 def is_pure_digit(n): valid {2, 3, 5, 7} while n 0: if n % 10 not in valid: return False n // 10 return True # 注意n0时循环不执行返回True但n0会在is_prime中被判False count 0 for num in range(2, limit 1): # 从2开始1不是质数 if is_pure_digit(num) and is_prime(num): count 1 return count # 测试 limit 20210605 result count_pure_primes_naive(limit) print(f1到{limit}之间的纯质数个数为{result})代码解析与注意事项主循环从2开始因为1不是质数且其数位“1”也不合法可以直接跳过。判断顺序是先is_pure_digit后is_prime这是基于我们之前分析的性能考虑。在is_pure_digit函数中对于num0的情况循环条件while n 0不成立直接返回True。但num0根本不会进入主循环从2开始且即使进入is_prime(0)也会返回False所以最终结果不受影响。这是一种隐式的正确性但如果你追求绝对严谨可以在is_pure_digit开头加上if n 0: return False。性能分析这个方法需要遍历大约2千万个数对每个数进行数位检查O(log n)并对其中通过检查的数进行质数判断O(√n)。虽然通过数位检查过滤掉了大部分数字只包含2,3,5,7的数字是极少数但整体运算量依然很大。在我的测试环境中普通笔记本电脑计算到20210605可能需要数十秒甚至更长时间这在竞赛的时限通常1-2秒内是无法接受的。因此遍历法更适合用于理解思路或者数据范围很小比如10^5以内的情况。3.2 解法二筛法预处理法竞赛推荐为了提高效率我们采用埃拉托斯特尼筛法预先计算出范围内所有数的质数标记然后再遍历判断。def count_pure_primes_sieve(limit): # 步骤1使用埃氏筛标记所有质数 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]: # 从i*i开始标记步长为i start i * i step i # 使用切片赋值可能更快但这里用循环更清晰 for j in range(start, limit 1, step): is_prime[j] False # 步骤2遍历并判断纯质数 def is_pure_digit(n): valid {2, 3, 5, 7} while n 0: if n % 10 not in valid: return False n // 10 return True count 0 for num in range(2, limit 1): if is_pure_digit(num) and is_prime[num]: count 1 return count # 测试 limit 20210605 result count_pure_primes_sieve(limit) print(f1到{limit}之间的纯质数个数为{result})代码解析与优化点筛法实现细节外层循环只需到sqrt(limit)。内层标记合数时从i*i开始因为小于i*i的i的倍数例如i*2,i*3, ...,i*(i-1)已经被更小的质数2,3,...,i-1标记过了。这是埃氏筛的标准优化。空间与时间权衡我们创建了一个长度为limit1的布尔列表。对于limit20210605这大约需要20MB内存每个布尔值在Python中实际上是一个对象占用更大可以使用array(b)或bytearray优化但代码会稍复杂。在竞赛允许的内存限制通常128MB或256MB内这是可行的。预处理的时间复杂度约为O(n log log n)在千万级别数据量上Python实现可能需要几秒时间。查询效率预处理后判断一个数是否为质数只需要O(1)的时间。结合数位检查整体的遍历判断部分非常快。实测对比在我的环境中筛法解法处理limit20210605总耗时大约在5-8秒取决于CPU性能虽然仍可能接近某些严格赛题的时间边缘但相比纯遍历法的几分钟已经是巨大的提升。这是竞赛中处理此类问题的通用且可靠的方法。3.3 解法三DFS生成法思维进阶这是最符合“纯质数”数位特性的高效方法。我们不需要遍历所有自然数而是直接生成所有由数字{2,3,5,7}组成的数然后只对这些生成的数进行质数判断。如何生成我们可以把问题看作构建一个多位数每一位有4种选择。这可以通过深度优先搜索DFS递归实现。def count_pure_primes_dfs(limit): # 质数判断函数同样可以用筛法优化这里为了对比用试除 def is_prime(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 digits [2, 3, 5, 7] count 0 def dfs(current): nonlocal count # 如果当前数已经超过上限则终止这条分支 if current limit: return # 如果当前数不为0避免把0算进去且是质数则计数 if current 0 and is_prime(current): count 1 # 继续在当前数后面添加一位数字 for d in digits: next_num current * 10 d dfs(next_num) # 从0开始搜索0乘以10再加d就是d本身这样能生成所有1位及以上的数 dfs(0) return count # 测试一个较小的范围验证正确性 limit_test 1000 result_dfs count_pure_primes_dfs(limit_test) print(fDFS生成法1到{limit_test}之间的纯质数个数为{result_dfs}) # 为了对比我们用筛法也算一下 result_sieve count_pure_primes_sieve(limit_test) print(f筛法1到{limit_test}之间的纯质数个数为{result_sieve})代码解析dfs(current)函数是核心。current表示当前已经生成的数字。首先判断current是否超过上限limit超过则返回剪枝。然后如果current大于0避免把初始的0当作一个数并且是质数就计入结果。最后遍历四个质数数字[2,3,5,7]将每个数字d附加到current的末尾即current * 10 d形成新的数字并递归调用dfs。初始调用dfs(0)会生成所有以2,3,5,7开头的数字并递归地生成所有位数。优势与局限优势需要检查的数字数量极少。在1到20210605范围内由{2,3,5,7}组成的数字数量是有限的。最大位数是8位因为20210605是8位数总数量最多是4^1 4^2 ... 4^8 (4*(4^8 -1))/(4-1) ≈ 349,525个。我们只需要对这大约35万个数字进行质数判断计算量比筛法遍历2千万个数字小得多。局限递归深度。生成8位数递归深度为8这在Python的递归限制内是完全安全的。但是如果范围极大需要生成非常长的数字则需要注意递归深度问题可以用栈来模拟递归避免此问题。注意上面的DFS代码中质数判断用的是试除法。对于35万个数字每个都用试除法判断如果数字很大接近上限试除法开销也不小。一个更高效的组合策略是先用DFS生成所有候选数然后用筛法预处理出limit范围内的质数表最后用O(1)的时间查询每个候选数是否为质数。这样结合了两种方法的优点。结合筛法的DFS优化版def count_pure_primes_optimized(limit): # 1. 筛法预处理质数表 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, limit 1, i): is_prime[j] False # 2. DFS生成候选数并计数 digits [2, 3, 5, 7] count 0 def dfs(current): nonlocal count if current limit: return if current 0 and is_prime[current]: count 1 for d in digits: next_num current * 10 d # 一个小优化如果next_num已经大于limit可以提前终止这个循环 # 因为digits是正数next_num随d增大而增大如果当前d构成的next_num已超限后面的d也会超限 # 但这里digits无序所以保留完整循环。如果digits是排序的可以break。 dfs(next_num) dfs(0) return count这个版本应该是本题在Python环境下最优的解法。它既避免了遍历大量无关数字又将质数判断的复杂度降到了O(1)。实际运行起来对于limit20210605速度非常快远低于1秒。4. 竞赛实战中的陷阱与调试技巧即使掌握了最优算法在竞赛的紧张环境中依然可能因为细节问题导致失分。下面我总结几个在解决“纯质数”问题时容易踩的坑以及相应的调试方法。4.1 边界条件0和1的处理这是最容易出错的地方。题目通常要求统计“从1到N”的纯质数个数。数字11不是质数。在质数判断函数中必须包含if n 2: return False。同时1的数位是“1”不属于{2,3,5,7}所以也会被数位检查过滤掉。但为了逻辑严密质数判断函数必须正确处理1。数字00不是质数其数位“0”也不合法。在我们的遍历法中循环通常从2开始不会遇到0。在DFS生成法中我们从current0开始递归但在计数时判断了if current 0从而排除了0。关键点如果你的数位检查函数是while n 0的循环那么输入0时会直接跳过循环返回True。你必须确保0不会通过质数判断即is_prime(0)返回False或者在你的数位检查中显式处理0。建议编写一个统一的is_pure_prime(n)函数进行测试覆盖边界案例def is_pure_prime(n, is_prime_listNone): 判断n是否为纯质数可传入预计算的质数表 # 数位检查 if n 0: return False valid_digits {2,3,5,7} temp n while temp 0: if temp % 10 not in valid_digits: return False temp // 10 # 质数检查 if is_prime_list is not None: return is_prime_list[n] else: # 使用试除法 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 # 测试边界 test_cases [0, 1, 2, 3, 4, 5, 13, 23, 29, 37, 100] for num in test_cases: print(f{num}: {is_pure_prime(num)}) # 期望输出0:False, 1:False, 2:True, 3:True, 4:False, 5:True, 13:False, 23:True, 29:False, 37:True, 100:False4.2 算法效率与竞赛时限蓝桥杯等竞赛对时间和空间都有严格限制通常C/C/Java是1-2秒Python可能放宽但也不多。对于本题遍历过滤法朴素在N2*10^7时极可能超时不推荐。筛法预处理法在Python中处理2*10^7筛的过程可能需要几秒有风险但有时能通过取决于具体比赛环境和数据强度。这是一种稳妥的“通用解”如果时间紧张且你想不出生成法可以尝试。DFS生成筛法查询是最优解速度快内存占用相对筛法遍历更少只需要质数表不需要遍历所有数强烈推荐。时间估算练习在本地编写代码后一定要用题目给定的最大范围或稍大一些进行测试记录运行时间。Python中可以使用time模块import time start time.time() result count_pure_primes_optimized(20210605) end time.time() print(f结果: {result}, 耗时: {end-start:.2f}秒)如果耗时远超过1秒就需要考虑优化比如检查筛法的循环是否写了低效代码或者DFS是否有不必要的递归。4.3 大数的质数判断与溢出问题本题范围在2*10^7内用32位整数足够。但在其他变体问题中范围可能更大。需要注意Python整数无溢出问题但循环条件i * i n中的i*i可能会变得非常大。对于极大的n比如10^12i*i可能超出普通整数范围但在Python中没问题。不过计算大数的平方根和乘法会变慢。试除法的优化上限对于极大的n试除法需要循环到√n如果n是10^12则需要循环到10^6次数太多可能超时。此时需要更高级的质数测试算法如Miller-Rabin但这超出了蓝桥杯通常的考察范围。4.4 调试与验证从小数据开始在编写完代码后不要立刻用最大数据测试。先从小范围开始验证正确性。手工列举列出1-100之间所有的纯质数2, 3, 5, 7, 23, 37, 53, 73。用你的程序计算1-100的结果看是否为8。对拍写一个暴力但正确的程序比如遍历法范围小的时候它是对的和你的优化程序筛法或DFS在较小范围如1-10000内比较结果确保两者输出一致。输出中间结果在调试时可以输出找到的纯质数列表检查是否有遗漏或错误包含。例如检查是否包含了13不应该包含因为1不是质数数字或29不应该包含因为9不是质数数字。def list_pure_primes(limit): # ... 使用你的优化算法但改为收集列表 ... pure_primes [] # 在判断为纯质数时执行 pure_primes.append(num) return pure_primes print(list_pure_primes(100)) # 应该输出 [2, 3, 5, 7, 23, 37, 53, 73]5. 举一反三相关问题与扩展思考掌握了“纯质数”的解法我们可以看看一些相关的变体问题这有助于深化理解。5.1 变体一计算纯质数之和如果题目不是求个数而是求和我们的算法只需要稍作修改。在计数的地方累加数字本身即可。def sum_pure_primes(limit): # 使用优化版DFS筛法 is_prime [True] * (limit 1) # ... 筛法代码省略 ... digits [2,3,5,7] total 0 def dfs(current): nonlocal total if current limit: return if current 0 and is_prime[current]: total current for d in digits: next_num current * 10 d dfs(next_num) dfs(0) return total注意求和可能很大确保使用Python的整数无限精度没有问题。5.2 变体二第K个纯质数有时题目会问第N个纯质数是多少。我们无法直接计算但可以在生成过程中计数。def find_kth_pure_prime(k, limit10**9): 在不超过limit的范围内查找第k个纯质数若不足则返回-1 is_prime [True] * (limit 1) # ... 筛法代码注意limit可能很大需要优化内存或使用分段筛 ... digits [2,3,5,7] count 0 def dfs(current): nonlocal count if current limit: return if current 0 and is_prime[current]: count 1 if count k: raise FoundException(current) # 用一个异常来跳出深层递归 for d in digits: next_num current * 10 d dfs(next_num) class FoundException(Exception): def __init__(self, value): self.value value try: dfs(0) return -1 # 没找到第k个 except FoundException as e: return e.value这里用异常来在找到目标后快速退出所有递归是一种非主流的控制流方式。更清晰的做法是让DFS函数返回一个状态标志。5.3 扩展思考不同进制下的“纯质数”这是一个更有趣的扩展。题目定义是基于十进制的。如果我们考虑二进制呢在二进制下“每一位都是质数”意味着每一位只能是1因为二进制只有0和1而1不是质数这显然无解。所以“纯质数”这个概念强烈依赖于进制。我们可以定义一个函数判断一个数在b进制下是否每一位都是质数这里的“质数数字”指十进制下的质数数字但表示在b进制下。这会涉及到进制转换和数字处理难度更大。例如在八进制下合法的质数数字仍然是{2,3,5,7}因为八进制数字0-7中只有这四个是质数。那么(23)_8十进制19在八进制下每一位是2和3都是质数数字且19本身是质数所以19是八进制下的“纯质数”。你可以尝试修改代码来解决这个问题这能很好地锻炼你对进制和数位处理的理解。5.4 性能优化进阶迭代生成与剪枝我们的DFS是递归的。对于特别大的范围比如需要生成几十位数字递归可能导致栈溢出。我们可以用栈stack来模拟递归过程实现迭代版的DFS。def count_pure_primes_iterative(limit): is_prime [True] * (limit 1) # ... 筛法代码省略 ... digits [2,3,5,7] count 0 stack [0] # 初始状态当前数字为0 while stack: current stack.pop() if current limit: continue if current 0 and is_prime[current]: count 1 # 注意为了和递归顺序一致从小到大可能需要逆序压栈 for d in reversed(digits): next_num current * 10 d if next_num limit: # 剪枝 stack.append(next_num) return count迭代实现避免了递归深度的限制并且可以通过if next_num limit进行更积极的剪枝。最后关于蓝桥杯的备考这道“纯质数”题给我们一个启示竞赛题往往考察的是对基础知识的综合运用和优化能力。它涉及了循环、递归、数论、筛法、DFS等知识点。在平时练习时不能满足于一种解法要多思考“有没有更优的方法”“边界情况是什么”“如何验证正确性”。把这些细节都琢磨透了在考场上才能游刃有余。