1. 从一道“简单”的质数题说起Torry的困惑与算法思维的起点如果你正在准备蓝桥杯或者刚开始接触算法竞赛那么“Torry的困惑(基本型)”这道题大概率是你绕不开的一道坎。乍一看题目描述——计算前n个质数的乘积然后取模——这有什么难的不就是筛个质数然后乘起来吗很多新手包括当年的我都会这么想然后兴冲冲地写一个最朴素的质数判断循环提交结果往往是“运行超时”或者“答案错误”。这道题编号ALGO-51属于蓝桥杯算法训练板块它真正的价值远不止于让你学会判断质数。它更像是一个“思维检测器”粗暴地把你从“能写出代码”的层面拉到了“需要考虑效率与边界”的算法竞赛入门级台阶上。我第一次做这道题时就栽在了两个地方一是对“前n个质数”的理解偏差二是完全没有考虑数据规模和取模运算的时机。我以为n最大也就1000吧结果一查n的范围可以到10000甚至更大。用O(n√n)的暴力判断法在n10000时你需要判断的数字可能超过十万每个数还要做√n次试除计算量瞬间爆炸。更关键的是题目要求对结果取模50000。这里就藏着一个新手极易忽略的陷阱是在连乘的过程中不断取模还是全部乘完最后再取模这个选择直接关系到你的程序是否会因为中间结果过大而溢出。我见过不少代码逻辑完全正确质数也筛对了但就是因为没有在乘法过程中及时取模导致计算到几十个质数时乘积就超出了int甚至long long的范围结果自然错了。所以今天我们就来彻底拆解这道题。我不会只给你一个AC的代码那样毫无意义。我会带你走一遍完整的解题心路从最直观但错误的想法开始分析它为什么不行然后一步步优化引入更高效的算法并深入探讨那些看似简单实则关键的细节。无论你是算法新手还是想巩固基础相信这篇内容都能让你对质数处理、模运算和算法优化有一个更扎实的理解。2. 问题本质解析到底在考我们什么在动手写任何一行代码之前我们必须像侦探一样把题目的每一个字都“审”清楚。题目全称是“Torry的困惑(基本型)”我们先把它的核心诉求翻译成程序员能理解的语言。2.1 输入与输出的精确解读题目通常会这样描述我们根据常见竞赛题格式还原输入一个整数n (1 ≤ n ≤ 10000)。 输出前n个质数的乘积对50000取模的结果。这里有几个必须抠死的点“前n个质数”这里的顺序是自然数序列中的质数从小到大。即2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ...新手易错点误认为是“小于等于n的所有质数”。如果n5前者是求第1到第5个质数2,3,5,7,11的乘积后者是求所有≤5的质数2,3,5的乘积。这完全是两个结果。“乘积对50000取模”数学上就是(p1 * p2 * ... * pn) % 50000其中pi是第i个质数。核心陷阱p1 * p2 * ... * pn这个数字增长极其恐怖。前20个质数的乘积就已经是一个19位数远超任何基本数据类型的表示范围C的long long最大约9e18Python的大整数虽无上限但连续大数乘法效率会降低。因此必须在乘法运算过程中就进行取模利用模运算的分配律(a * b) % m ((a % m) * (b % m)) % m来保证中间结果始终可控。数据范围 n ≤ 10000这是决定我们算法复杂度的关键。我们需要找到第10000个质数。根据质数定理第n个质数pn大约在n * ln(n)这个量级。对于n10000第10000个质数大概在10000 * ln(10000) ≈ 10000 * 9.21 ≈ 92100 附近。实际上第10000个质数是104729。这意味着我们的质数筛法或判断范围至少要覆盖到10万这个量级。2.2 性能要求与算法选型分析基于以上分析我们可以对可能的解决方案进行一个初步的评估方案A对每个候选数进行试除法判断。对于每个数i检查它是否能被2到sqrt(i)之间的任何整数整除。为了找到前n个质数我们需要从2开始逐个判断直到找到第n个为止。时间复杂度粗略估算为 O(n * √pn)。当n10000, pn≈10^5时计算次数约为 10000 * √100000 ≈ 10000 * 316 ≈ 3.16e6。这个计算量对于现代计算机在1秒内完成是可行的但已经处于临界点且代码如果写得不高效比如在循环条件上有多余计算很容易超时。评价勉强可行但不优雅是下策。它没有利用质数之间的内在联系做了大量重复判断。方案B埃拉托斯特尼筛法埃氏筛。预先分配一个布尔数组isPrime[0..MAX]初始假设所有数都是质数然后从2开始将其倍数全部标记为非质数。筛选完毕后数组中剩下的true对应的就是质数。时间复杂度O(n log log n)其中n是筛的范围例如MAX110000。这个效率远高于试除法。空间复杂度O(MAX)需要一个大数组。评价本题的推荐标准解法。对于MAX110000筛法运行速度极快可以瞬间得到从2到MAX的所有质数然后我们直接取前n个即可。思路清晰代码简洁性能有保障。方案C欧拉线性筛。埃氏筛的一个优化版本确保每个合数只被其最小质因子筛掉一次时间复杂度严格O(n)。评价性能最优但代码稍复杂。对于本题的数据范围埃氏筛已绰绰有余。线性筛更像是一种“炫技”或为更大数据规模准备。我们可以作为拓展知识了解。显然方案B埃氏筛是解决本题最平衡、最可靠的选择。它完美契合了“一次性找出足够多质数”的需求并且算法本身非常经典是竞赛入门必备技能。接下来我们就重点实现它并处理取模的细节。3. 核心工具构建高效质数筛法的实现与优化我们选择埃拉托斯特尼筛法作为核心引擎。这个算法的思想非常直观好比用一个筛子过滤自然数把合数筛掉留下质数。3.1 埃氏筛的基本步骤与代码实现假设我们需要所有小于等于MAX_N的质数。创建一个布尔数组is_prime[MAX_N 1]初始化所有元素为True假设都是质数。将is_prime[0]和is_prime[1]设为False因为0和1不是质数。从i 2开始遍历到sqrt(MAX_N)因为一个合数必然有一个不大于其平方根的质因子如果is_prime[i]为True那么i是一个质数。然后将i的所有倍数从i*i开始到MAX_N结束步长为i标记为False即非质数。为什么从i*i开始因为比i*i小的i的倍数如2*i,3*i, ...,(i-1)*i已经被更小的质数2, 3, ..., i-1筛过了。遍历结束后所有is_prime[j]为True的j就是质数。用Python实现这个基础版本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 for j in range(i * i, limit 1, i): is_prime[j] False # 收集所有质数 primes [i for i, flag in enumerate(is_prime) if flag] return primes3.2 针对本题的定制化优化上面的代码是通用筛法。对于本题我们需要做几处针对性的优化和设计确定筛法的上限MAX_N我们需要找到第n个质数。但n是输入值我们无法预先知道第n个质数具体是多少。一个稳妥的方法是估计一个足够大的上限。根据前面分析第10000个质数约104729。为了保险起见我们通常设置MAX_N 110000或120000甚至可以更大一些如150000以确保一定能筛出前10000个质数。多筛一些数对性能影响微乎其微。只筛选不立即存储基础版本最后通过列表推导式收集所有质数这会额外遍历一次整个is_prime数组。对于本题我们可以在筛的过程中一旦发现质数i就将其存入一个列表prime_list中。这样当prime_list的长度达到n时我们就可以提前结束筛选吗注意不行因为埃氏筛的过程是标记合数我们必须完整运行完整个筛法流程才能保证is_prime数组的正确性。我们不能在找到第n个质数时就跳出外层循环否则后面更大的质数的倍数可能还没被标记为合数导致is_prime数组状态错误。不过外层循环的终点是sqrt(MAX_N)这比MAX_N小很多所以完整的筛法代价是可以接受的。空间优化可选使用bytearray或array(b)代替list来存储布尔值可以节省一些内存。对于MAX_N150000一个布尔列表约占150KB内存压力很小所以这个优化不是必须的。循环步长优化在标记质数i的倍数时我们可以进行一个微优化。对于偶数质数2我们按步长2标记。对于大于2的奇数质数i其倍数i * i是奇数i * i i是偶数奇奇偶而所有大于2的偶数都已经被质数2筛过了。因此我们可以将步长设置为2*i只标记奇数倍的合数。这个优化可以减少大约一半的标记操作。结合以上几点我们写出针对本题优化后的筛法函数def get_first_n_primes(n): # 估算一个足够大的上限确保能包含第n个质数 # 一个简单的估计第n个质数大约 n * (log(n) log(log(n)))这里直接取大一点 if n 10: limit 30 else: # 对于n10000, 这个公式给出约114000我们取130000确保安全 limit int(n * (math.log(n) math.log(math.log(n)))) 1000 # 或者直接固定一个足够大的数如200000 # limit 200000 is_prime bytearray(b\x01) * (limit 1) # 使用bytearray节省内存 is_prime[0] is_prime[1] 0 primes [] sqrt_limit int(limit ** 0.5) # 单独处理质数2 if limit 2: primes.append(2) # 标记所有偶数除了2 for j in range(2*2, limit 1, 2): is_prime[j] 0 # 只遍历奇数 for i in range(3, sqrt_limit 1, 2): if is_prime[i]: primes.append(i) # 从i*i开始标记步长为2*i只标记奇数倍 start i * i step 2 * i for j in range(start, limit 1, step): is_prime[j] 0 # 收集剩余未遍历到的质数大于sqrt_limit的 start_num sqrt_limit 1 if sqrt_limit % 2 0 else sqrt_limit 2 for i in range(start_num, limit 1, 2): if is_prime[i]: primes.append(i) if len(primes) n: # 一旦收集到足够质数可以提前结束收集循环 break return primes[:n] # 返回前n个这个版本的筛法更加高效并且直接返回我们所需的前n个质数列表。4. 解题全流程实现与关键细节剖析有了高效的质数生成器解决整个问题就剩下主逻辑的串联了。主逻辑非常简单读入n获取前n个质数列表计算它们的乘积并对50000取模输出结果。但恰恰是这简单的几步藏着几个必须注意的“坑”。4.1 主逻辑框架与模运算处理import sys import math def main(): n int(sys.stdin.readline().strip()) MOD 50000 # 1. 获取前n个质数 primes get_first_n_primes(n) # 使用上一节优化后的函数 # 2. 计算乘积并取模 result 1 for prime in primes: result (result * prime) % MOD # 关键步步取模防止溢出 # 3. 输出结果 print(result) if __name__ __main__: main()这段代码的核心在于第2步的循环result (result * prime) % MOD。我们来深入分析一下为什么必须这么做以及如果做错了会发生什么。4.2 模运算的时机为什么不能最后再取模假设我们计算前5个质数的乘积2 * 3 * 5 * 7 * 11 2310。2310 % 50000 2310。这看起来没问题因为2310小于50000。但让我们看一个更大的例子。前10个质数的乘积是 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 6469693230。 这个数字大约64亿还在64位整数(long long)的表示范围内约9e18。然而前20个质数的乘积已经是一个19位数约9.69e18这已经逼近了64位整数的上限。前30个质数的乘积约2.33e28则远远超出了任何基本整数类型能直接表示的范围。在C、Java等语言中如果你使用int或long long来存储连乘的中间结果在乘到十几二十个质数时结果就会溢出变成一个完全错误的负数或乱码最后再对这个错误的结果取模答案自然是错的。在Python中虽然大整数可以表示任意大的数不会溢出但连续计算大整数的乘法效率会显著下降当n很大时比如接近10000可能会带来不必要的性能开销甚至在某些有运行时间限制的评测环境中导致超时。因此在每一步乘法后立即取模是解决此类问题的标准做法。这基于模运算的以下性质(a * b) % m ((a % m) * (b % m)) % m所以result始终保持在[0, MOD-1]的范围内永远不会溢出并且计算效率极高。4.3 边界条件与输入处理n1的情况前1个质数是2乘积是22 % 50000 2。我们的代码能正确处理。n0的情况题目通常规定 n ≥ 1所以一般不需要处理。但如果考虑健壮性可以判断一下如果n0则乘积定义为1空乘积为1输出 1 % 50000 1。输入读取使用sys.stdin.readline()比input()在大量输入时更快。对于本题只有一行输入区别不大但养成好习惯很重要。4.4 完整可提交的代码示例将筛法函数和主逻辑整合并添加必要的导入和注释就得到了一个健壮、高效的解决方案import sys import math def get_first_n_primes(n): 使用优化的埃拉托斯特尼筛法获取前n个质数。 采用bytearray存储状态并对奇数质数使用2*i步长进行优化。 if n 0: return [] # 估算筛选上限确保足够找到第n个质数 # 一个简单且安全的估计当n较大时第n个质数小于 n*(log n log log n) # 这里为了绝对安全我们直接取一个较大的固定值如200000。 # 因为n最大10000第10000个质数~104729200000足够。 LIMIT 200000 is_prime bytearray(b\x01) * (LIMIT 1) is_prime[0] is_prime[1] 0 primes [] # 单独处理质数2 if LIMIT 2: primes.append(2) # 标记所有偶数除了2本身 for j in range(4, LIMIT 1, 2): is_prime[j] 0 # 只遍历奇数 sqrt_limit int(math.isqrt(LIMIT)) for i in range(3, sqrt_limit 1, 2): if is_prime[i]: primes.append(i) # 从i*i开始步长为2*i只标记奇数倍 start i * i step i * 2 # 防止start超过LIMIT导致range出错 for j in range(start, LIMIT 1, step): is_prime[j] 0 # 收集大于sqrt_limit的剩余质数 # 从大于sqrt_limit的第一个奇数开始 start_num sqrt_limit 1 if sqrt_limit % 2 0 else sqrt_limit 2 for i in range(start_num, LIMIT 1, 2): if is_prime[i]: primes.append(i) # 提前终止条件已经收集到足够多的质数 if len(primes) n: break # 返回前n个质数 return primes[:n] def main(): data sys.stdin.read().strip().split() if not data: return n int(data[0]) MOD 50000 primes get_first_n_primes(n) result 1 for prime in primes: result (result * prime) % MOD print(result) if __name__ __main__: main()注意这里使用了math.isqrt(LIMIT)来计算整数平方根它比int(LIMIT**0.5)更精确、更快尤其是在处理大整数时。5. 算法扩展与思维提升从“基本型”到“进阶型”解决了“基本型”我们的思考不能止步于此。真正的算法训练是举一反三是思考题目可能的变种和更优的解法。这能帮助你在赛场上遇到新题时快速找到思路。5.1 如果n非常大比如n10^6当n达到百万级别时我们之前设定的固定上限LIMIT200000就远远不够了。第100万个质数大约是15485863。我们不能再盲目地设置一个巨大的固定上限那会浪费大量内存和时间。解决方案动态扩大筛选范围我们可以实现一个分段筛法。先筛一个较小的范围比如10^6如果找到的质数不足n个就接着筛下一段。这样可以避免一次性分配超大数组。使用线性筛欧拉筛埃氏筛的时间复杂度是O(n log log n)而线性筛是严格的O(n)。在n极大时线性筛的优势会更明显。其核心思想是让每个合数只被它的最小质因子筛掉一次。def linear_sieve(n): primes [] is_composite [False] * (n 1) for i in range(2, n 1): if not is_composite[i]: primes.append(i) for p in primes: if i * p n: break is_composite[i * p] True if i % p 0: # 保证每个合数只被最小质因子筛掉 break return primes要获取前N个质数我们需要估计一个足够大的上限n来运行这个筛法。线性筛的代码比埃氏筛稍复杂但理解了“最小质因子”这个关键点后就非常清晰了。5.2 如果模数M非常大且不是质数本题的模数50000是一个较小的合数。如果模数M非常大比如10^97并且题目要求计算的是前n个质数的乘积模M我们的核心方法步步取模依然有效因为模运算的性质与模数大小无关。但如果问题不再是简单的连乘取模而是涉及到除法比如求前n个质数的乘积除以某个数再取模那么就需要用到模逆元的概念这通常要求模数M是质数才能保证逆元存在。这就进入了数论的更深领域。5.3 如果问题变成“求前n个质数之和模M”呢这看起来更简单了直接把连乘改成连加即可。但这里隐藏了一个和乘积同样重要的问题整数溢出。前n个质数的和增长也很快n10000时和大约在5.7亿左右仍在64位整数范围内但n再大一些也会溢出。因此同样需要在求和过程中步步取模sum (sum prime) % M。这个变种题常常用来考察选手是否真正理解了“在运算过程中取模以防止溢出”这一思想而不是死记硬背“乘积要取模”。5.4 关于质数判断的其他方法除了筛法在特定场景下还有其他判断质数的方法Miller-Rabin素性测试一种概率性算法对于极大的整数远超64位它可以在极短时间内以极高的概率判断其是否为质数。它基于费马小定理和二次探测定理。这在需要判断单个超大整数是否为质数时非常有用但不适用于需要批量生成连续质数的情况。6n±1法则所有大于3的质数都可以表示为6n±1的形式。这可以作为一个快速的初步筛选在试除法中用来跳过一些明显的合数如偶数、3的倍数。例如在试除时可以先检查2和3然后从5开始每次递增2和4即检查5, 7, 11, 13, 17, 19...。这能将试除次数减少大约三分之一。对于“Torry的困惑”这类需要连续质数的问题筛法依然是唯一且最佳的选择。Miller-Rabin适用于点判断6n±1是试除法的优化但效率仍远低于筛法。6. 常见错误排查与调试心得即便理解了算法实际编码时还是会遇到各种问题。下面是我在解决这类题目和教学过程中总结出的几个最常见的“坑”及其解决方法。6.1 错误结果输出为0症状程序运行很快但输出结果是0尤其是当n稍微大一点的时候比如n10。可能原因1模运算错误。# 错误写法 result result * prime % MOD # 这看起来和 (result * prime) % MOD 一样在Python中乘法和取模运算符优先级相同从左到右结合。所以result * prime % MOD等价于(result * prime) % MOD这本身没错。但如果你不小心写成了result * prime % MOD那就完全错了这等价于result result * (prime % MOD)意味着你每次乘的都是prime对50000取模后的值。当prime是50000的倍数时当然质数不可能是50000的倍数或者更关键的是当result本身是50000的倍数时后续任何乘法结果都是50000的倍数最后取模就是0。更常见的是你错误地在循环外一次性取模# 错误写法 product 1 for prime in primes: product * prime result product % MOD # 此时product可能已经溢出在其他语言中或极其巨大在C/Java中product会溢出导致错误在Python中虽然不会溢出但计算大数乘积效率低。解决方法坚持使用result (result * prime) % MOD这种最清晰的写法避免歧义。可能原因2质数列表错误。 如果你的筛法有bug导致质数列表包含了非质数比如1或者顺序不对。例如如果错误地将1包含在内那么乘积从一开始就是0因为任何数乘以1还是原数但1不是质数说明逻辑有误但更可怕的是如果包含了0那乘积直接变0。检查你的筛法初始化部分确保is_prime[0]和is_prime[1]被正确设置为False。调试方法打印出前10个你找到的“质数”看看是不是[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]。6.2 错误运行超时TLE症状程序长时间运行没有结果或者被评测系统判定超时。可能原因1使用了未优化的试除法。 这是最常见的超时原因。对于每个候选数i从2循环到i-1或者到sqrt(i)来判断。当需要找到第10000个质数时你需要判断大约10万个数字每个数字最坏要循环sqrt(i)≈316次总共是千万次级别的操作在Python中可能就在超时的边缘。解决方法毫不犹豫地换用埃氏筛。对于本题范围埃氏筛的复杂度是O(n log log n)速度极快。可能原因2筛法实现效率低下。 即使用了筛法如果实现不好也会超时。内层循环的起点和步长务必从i*i开始步长为i。如果从2*i开始会做大量重复标记。使用Python原生列表的频繁赋值is_prime[j] False在列表很大时如果使用普通的list速度尚可。但使用bytearray或array(b)会有小幅性能提升更重要的是节省内存。外层循环终点应该是sqrt(limit)而不是limit。筛到sqrt(limit)就足以标记出所有合数了。可能原因3输入读取。 虽然本题只有一行输入但如果你在处理多组输入其他题目时使用了input()在数据量很大时可能会成为瓶颈。使用sys.stdin.read()一次性读取所有输入再处理会快得多。调试方法在你的本地环境中用最大的n10000测试你的程序看看运行时间是否在1秒以内。可以使用time模块计时。6.3 错误答案错误WA但样例能过症状自己测试的小样例都正确但提交后显示答案错误。可能原因1对“前n个质数”的理解错误。 这是最隐蔽的错误。你的程序可能计算的是“小于等于n的质数”的乘积。请再次仔细审题。验证方法计算n5时你的输出。如果是“小于等于n的质数”质数有2,3,5乘积30模50000得30。如果是“前n个质数”质数是2,3,5,7,11乘积2310模50000得2310。用这个简单的案例就能验证。可能原因2模数50000写错了。 比如写成了5000或者500000。仔细检查常量定义。可能原因3质数列表数量不足。 你的筛法上限LIMIT设置得太小导致没有找到足够的n个质数。例如你需要前10000个质数但你的筛只找到了8000个那么你的primes列表长度可能只有8000如果你没有检查长度就切片或者切片primes[:n]会得到不足10000个元素的列表如果列表长度小于n切片不会报错但结果列表长度小于n。用这个错误的列表去计算乘积结果自然不对。验证方法在获取质数列表后立即检查len(primes)是否大于等于n。可以在代码中添加断言assert len(primes) n。可能原因4整数溢出仅限C/Java等语言。 在Python中我们不用担心这个但如果你用C写即使步步取模也要确保用来乘法的中间变量类型足够大。result和prime相乘时即使result小于50000prime可能超过10万乘积可能超过50亿这需要用到64位的long long。在C中应使用long long result 1;并且在乘法时进行强制类型转换或使用1LL初始化。调试心法当遇到WA时不要只盯着代码看。应该构造一些小的、容易手算的测试用例比如n1,2,3,4,5分别手动计算出正确结果然后与你的程序输出对比。一旦发现某个n的输出不对就针对这个n进行调试打印出中间变量如质数列表往往能快速定位问题所在。