1. 项目概述从一道经典算法题说起最近在辅导几个准备参加蓝桥杯竞赛的学生他们不约而同地都卡在了同一道题上——“Torry的困惑(基本型)”。这道题在蓝桥杯的练习系统中被归类为“基本型”但恰恰是这种看似基础的题目最能考验一个程序员对算法核心思想的理解和代码实现的扎实程度。题目本身并不复杂给定一个正整数n要求计算前n个质数的乘积并对一个很大的数通常是50000取模。很多新手一看觉得不就是找质数然后累乘吗但一上手写不是超时就是结果不对最后陷入深深的“困惑”。这正是“Torry的困惑”这个题名的精妙之处它困惑的从来不是Torry而是每一个轻视它的小白。这道题的核心远不止于“求出前n个质数”。它实际上是一个综合性的练兵场至少融合了三个关键算法知识点质数筛法尤其是埃拉托斯特尼筛法的高效实现、大数运算中的取模技巧、以及边界条件与性能优化的平衡。在竞赛环境中n可能大到上万直接暴力判断每个数是否为质数然后累乘其时间复杂度是O(n * sqrt(m))其中m是第n个质数的大小这绝对是无法接受的。因此这道题逼着你必须掌握更高效的筛法并且理解在连续乘法中何时取模才不会影响最终结果。如果你正在准备蓝桥杯或任何编程竞赛或者你只是想巩固一下自己的算法基础那么彻底吃透这道题将让你受益匪浅。它不仅教你写出高效的质数筛更让你理解算法竞赛中“时间与空间”的权衡艺术。接下来我将以一个过来人的身份拆解这道题的每一个技术细节分享我调试了无数遍才总结出的最优解法和那些容易踩坑的地方。2. 核心需求与算法思路拆解2.1 问题本质与数学模型抽象首先我们把题目翻译成清晰的数学和编程语言。给定输入n我们需要找到从小到大的前n个质数p1, p2, p3, ..., pn。计算这些质数的乘积P p1 * p2 * p3 * ... * pn。输出 P % MOD 的结果其中MOD通常为50000。这里立刻引出了两个关键约束也是性能瓶颈所在约束A找质数的效率n可能很大例如10000第n个质数的大小m会远大于n。我们需要一个能在合理时间内找出前n个质数的算法。约束B大数处理的效率即使找到了这些质数它们的乘积P可能是一个天文数字远超任何编程语言中基本整数类型的表示范围。我们不能直接计算完整的P必须在计算过程中就进行取模操作。因此我们的算法设计必须同时解决这两个效率问题。一个低效的质数判断会拖慢整体速度而不恰当的大数处理会导致溢出或得到错误结果。2.2 算法选型为什么埃氏筛是更优解面对找质数初学者最容易想到的是“试除法”对于每个待判定的数num用2到sqrt(num)之间的所有整数去试除。这个方法对于单个数的判断是清晰的但用于连续找出前n个质数则效率低下。因为你需要对每个数都重复进行sqrt(num)次试除而很多数明明不是质数比如偶数也浪费了时间。更优秀的策略是“筛法”。最著名的两种是埃拉托斯特尼筛法埃氏筛和欧拉筛线性筛。埃氏筛核心思想是“标记”。假设我们要筛选出不超过范围上限N的所有质数。我们先假设所有数都是质数然后从2开始将2的所有倍数标记为非质数接着找到下一个未被标记的数一定是质数这里是3再将3的所有倍数标记掉……如此反复直到处理完所有数。最后所有未被标记的数就是质数。欧拉筛它保证了每个合数只被其最小质因子筛掉一次时间复杂度是严格的O(N)。理论上比埃氏筛的O(N log log N)更优。那么在这道题里该选哪个我强烈推荐使用埃氏筛。原因如下实现复杂度欧拉筛的实现需要多维护一个质数列表并且内层循环的条件判断更容易写错对初学者不友好。埃氏筛的逻辑直观几行代码就能实现不易出错。空间与时间的权衡虽然欧拉筛时间复杂度更低但埃氏筛的O(N log log N)对于本题的数据范围n10000, 第10000个质数大约在10^5量级来说已经绰绰有余在竞赛的时限内完全不是问题。“范围”已知性埃氏筛需要预先确定一个筛选范围N。我们虽然不知道第n个质数具体是多少但可以根据质数定理进行估算。一个非常安全且简单的经验公式是N max(10, n * (log(n) log(log(n))))。对于n10000这个值大约在15万以内内存开销很小。所以综合实现难度和性能埃氏筛是这道题的最佳拍档。我们先用埃氏筛在一个足够大的范围内筛选出所有质数然后直接取前n个进行计算。2.3 大数取模的核心技巧边乘边模解决了质数来源我们来看乘积计算。计算(a * b) % MOD如果a和b都很大直接乘可能会溢出。这里需要利用模运算的一个基本性质(a * b) % MOD ((a % MOD) * (b % MOD)) % MOD这意味着我们可以在乘法运算的每一步之后立即取模用中间结果参与下一次运算从而保证所有参与运算的数都不会超过MOD * MOD的范围在本题中MOD50000其平方也在普通整型安全范围内。因此我们的计算过程可以写成result 1 for prime in first_n_primes: result (result * prime) % MOD这个循环结束后的result就是最终答案。这里有一个至关重要的细节取模操作必须在每次乘法后立即进行而不是累乘完所有质数后再取模。3. 埃氏筛的Python实现与深度优化3.1 基础埃氏筛的实现让我们先写出最标准的埃氏筛。它的目标是生成一个布尔列表is_prime其中is_prime[i]为True表示数字i是质数。def eratosthenes_sieve(limit): 埃拉托斯特尼筛法返回一个布尔列表is_prime[i]表示数字i是否为质数。 :param limit: 筛选的上限包含 :return: list[bool] if limit 2: return [False] * (limit 1) is_prime [True] * (limit 1) is_prime[0] is_prime[1] False # 0和1不是质数 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关键点解析外层循环的终点for i in range(2, int(limit ** 0.5) 1)。为什么到sqrt(limit)就够了因为如果某个数x是合数那么它一定有一个不大于sqrt(x)的质因子。当我们用所有小于等于sqrt(limit)的质数去标记它们的倍数时所有小于等于limit的合数都必然被标记了。内层循环的起点for j in range(i * i, limit 1, i)。为什么从i*i开始考虑质数i5它的倍数5*210已经在i2时被标记5*315在i3时被标记5*420在i2时被标记。所以第一个未被更小质数标记的合数就是5*525。从i*i开始可以避免大量重复标记是埃氏筛一个重要的常数优化。3.2 确定筛选范围N的实用策略我们不知道第n个质数具体是多少所以需要估算一个足够大的上限limit确保这个范围内至少包含n个质数。理论估算利用质数定理第n个质数p_n约等于n * (log n log log n)。这是一个渐近估计对于小的n可能不准。工程实践一个简单粗暴且非常有效的方法是设置一个足够大的静态上限。根据蓝桥杯评测数据的特点n最大通常为10000第10000个质数小于150000。为了绝对安全我们可以将limit设置为200000甚至300000。对于现代计算机筛选30万以内的质数几乎是瞬间完成的内存占用也只有30万个布尔值约0.3MB完全可接受。动态估算推荐我们可以写一个简单的循环如果筛选出的质数数量不足n就扩大limit重新筛选。但为了避免在竞赛中因极端情况超时我建议直接使用一个稍大的静态值。在我的实现中我采用一个简单的动态估算作为下限并设置一个安全系数def estimate_limit(n): 估算包含前n个质数所需的最小上限。 if n 10: return 30 # 使用一个稍宽松的估计 n * (log(n) log(log(n))) * 1.2并确保至少为100 from math import log estimate int(n * (log(n) log(log(n))) * 1.2) return max(estimate, 100)在实际代码中我们可以直接使用limit 200000简单省心。3.3 从筛法结果中提取前n个质数获得is_prime列表后我们需要遍历它收集前n个为True的索引即质数本身。def get_first_n_primes(n, limit): is_prime eratosthenes_sieve(limit) primes [] for num in range(2, limit 1): if is_prime[num]: primes.append(num) if len(primes) n: break # 保险检查如果primes数量不足n说明limit设小了应报错或扩大limit if len(primes) n: raise ValueError(f筛选范围limit{limit}太小只找到{len(primes)}个质数需要{n}个。) return primes4. 完整解题代码与逐行解析将以上所有部分组合起来并处理好输入输出我们就得到了完整的解决方案。import sys MOD 50000 def eratosthenes_sieve(limit: int) - list[bool]: 埃拉托斯特尼筛法返回长度为limit1的布尔列表。 if limit 2: return [False] * (limit 1) is_prime [True] * (limit 1) is_prime[0] is_prime[1] False # 只需遍历到sqrt(limit) for i in range(2, int(limit ** 0.5) 1): if is_prime[i]: # 从i*i开始标记i的倍数 step i start i * i for j in range(start, limit 1, step): is_prime[j] False return is_prime def solve(): # 读取输入 data sys.stdin.read().strip().split() if not data: return n int(data[0]) # 估算一个足够大的上限这里直接取一个安全值 # 已知蓝桥杯测试数据n10000第10000个质数约104729这里取15万足够。 limit 150000 # 1. 筛出所有质数 is_prime eratosthenes_sieve(limit) # 2. 收集前n个质数 primes [] for num in range(2, limit 1): if is_prime[num]: primes.append(num) if len(primes) n: break # 3. 计算乘积并取模 result 1 for prime in primes: result (result * prime) % MOD # 4. 输出结果 print(result) if __name__ __main__: solve()代码关键点深度解析输入处理sys.stdin.read()一次性读取所有输入比多次调用input()更快是竞赛中的常用技巧。.strip().split()处理了可能的换行和空格。常量定义MOD 50000定义为全局常量代码更清晰也便于修改。筛法函数优化内层循环使用了局部变量step和start微小的优化但体现了编码习惯。limit的选择这里我直接选择了150000。这是一个基于经验的“安全值”确保能覆盖蓝桥杯所有测试用例同时不会造成不必要的内存浪费。你也可以根据n动态调整但静态值更简单可靠。乘积计算循环result (result * prime) % MOD是核心中的核心。它保证了在计算过程中result的值始终在[0, MOD-1]之间prime是质数本身小于limit两者相乘不会溢出Python的整数范围Python支持大整数但取模后可以保持数值较小是一种好习惯。循环终止条件在收集质数的循环中一旦primes长度达到n立即break避免无用的后续遍历。5. 性能分析与边界条件测试5.1 时间复杂度分析我们的算法主要耗时在两个部分埃氏筛时间复杂度为 O(limit * log log limit)。由于我们设定 limit ≈ 150000这个操作非常快。遍历筛选结果收集前n个质数最坏情况是O(limit)但通常远小于这个值因为我们在收集到n个质数后就停止了。计算乘积取模O(n)。因此整体时间复杂度由埃氏筛主导约为 O(limit * log log limit)对于limit150000这是一个常数级别的操作完全满足竞赛要求。5.2 空间复杂度分析我们使用了一个长度为limit1的布尔列表is_prime。在Python中一个布尔值实际上占用一个字节取决于解释器实现但通常不是一位。所以空间复杂度约为 O(limit) 字节对于limit150000大约是150KB内存消耗极小。5.3 边界条件与测试用例彻底测试是保证代码正确的关键。以下是一些必须考虑的测试用例输入n预期输出前n个质数乘积模50000测试目的12 % 50000 2最小输入测试32 * 3 * 5 30 % 50000 30小规模计算验证10前10个质数积为6469693230模50000为3230中等规模验证100需编程计算但结果应为一个四位数如xxx验证筛法范围是否足够10000蓝桥杯官方测试数据用于最终验证最大规模性能与正确性测试0题目通常保证n1但可考虑异常处理代码健壮性非必需注意在竞赛中务必确认题目对输入n范围的描述。如果明确n1则无需处理0或负数。但如果是通用函数则应添加相应的输入校验。我们可以写一个简单的测试函数来验证def test(): test_cases [(1, 2), (3, 30), (10, 3230)] for n, expected in test_cases: # 这里需要调用solve函数的核心逻辑或者将逻辑封装成一个函数便于测试 # 假设我们有一个函数 calculate(n) 返回结果 result calculate(n) # calculate函数是提取出来的解题逻辑 if result expected: print(fTest passed for n{n}: {result}) else: print(fTest FAILED for n{n}: expected {expected}, got {result})6. 常见错误与调试心得实录在帮助学生们调试这道题的过程中我见到了五花八门的错误。这里总结几个最典型的6.1 错误1暴力试除法导致的超时错误代码片段def is_prime(num): for i in range(2, num): # 或者 for i in range(2, int(num**0.5)1): if num % i 0: return False return True count, product, num 0, 1, 2 while count n: if is_prime(num): product * num count 1 num 1 print(product % MOD)问题分析即使试除范围优化到sqrt(num)对于大的n比如10000你需要判断大量的数直到第10000个质数大约10万。每个判断需要O(sqrt(num))次运算总时间复杂度接近O(n * sqrt(n log n))在Python中必然超时。解决方案必须改用筛法一次性批量找出质数。6.2 错误2取模时机错误错误代码片段product 1 for prime in primes: product * prime result product % MOD # 错误product可能已经巨大无比导致计算缓慢甚至溢出在某些语言中。问题分析在计算过程中product的值会以指数级增长很快就会超过Python大整数的有效处理范围虽然Python不会溢出但计算会变得极其缓慢占用大量内存在其他有整数上限的语言如C、Java中则会直接溢出得到错误结果。解决方案坚持“边乘边模”原则。6.3 错误3筛法范围limit设置过小错误现象当n较大时如10000程序可能提前退出循环因为找不齐n个质数或者陷入死循环如果没写退出条件导致运行时错误或答案错误。问题分析低估了第n个质数的大小。解决方案采用前文提到的“静态安全值”法。对于蓝桥杯limit150000是经过验证的安全值。如果追求精确可以写一个循环当找到的质数不足时将limit翻倍并重新筛选直到满足条件。但要注意设置最大重试次数以防无限循环。6.4 错误4埃氏筛内层循环的冗余操作错误代码片段for i in range(2, limit1): if is_prime[i]: for j in range(i*2, limit1, i): # 从i*2开始 is_prime[j] False问题分析从i*2开始标记而不是i*i会导致大量重复标记。例如当i5时会标记10已被2标记、15已被3标记等。虽然不影响最终结果的正确性但增加了不必要的操作影响性能。解决方案严格从i*i开始标记。6.5 调试心得如何验证你的筛法是正确的当你对筛法代码没把握时可以用小数据验证手动列出前20个质数2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71。将你的limit设为100运行筛法打印出所有is_prime[i]为True的i。对比两者是否一致。这是最直接有效的单元测试方法。7. 算法扩展与思维提升“Torry的困惑”虽然被标记为“基本型”但它为我们打开了算法优化世界的一扇门。掌握它之后你可以尝试思考以下扩展问题这能极大提升你的算法能力如果MOD不是一个较小的数而是一个非常大的质数例如10^97该怎么办挑战在计算(result * prime) % MOD时result和prime都小于MOD但它们的乘积可能超过64位整数的范围在C/Java中。解决方案需要使用快速乘取模算法或者直接使用Python其整数运算本身支持大数。在其他语言中可以写一个快速乘函数利用二分思想将乘法转化为加法避免溢出。如果题目要求计算的是“前n个质数之和模MOD”呢分析这看起来更简单但本质一样。依然需要高效地找到前n个质数然后将加法替换为乘法即可。但要注意加法取模(a b) % MOD同样可以边加边模。能否用欧拉筛线性筛实现效率提升多少实践建议作为练习你可以尝试实现欧拉筛。对于本题的数据规模你可能无法直观感受到时间差异因为都很快。但在一些对性能极端苛刻的场景或者当limit达到千万甚至上亿级别时欧拉筛的线性优势就会体现出来。实现欧拉筛的关键是理解if i % primes[j] 0: break这行代码它保证了每个合数只被筛一次。如何求解第n个质数思路这是另一个经典问题。我们可以利用筛法在筛选过程中计数当计数达到n时当前的数字就是第n个质数。这要求我们的limit必须足够大。通常结合质数定理估算和二分查找来高效求解。这道题就像一块试金石它检验的是你是否真正理解了“空间换时间”的筛法思想以及是否具备处理大数运算的基本素养。很多复杂的算法问题其内核就是这些基础思想的组合与变形。所以不要因为它被标为“基本型”而轻视沉下心来把它吃透你的编程内功会扎实很多。