1. 项目概述从一道题看筛法的实战价值“质数距离”这名字听起来有点抽象但如果你刷过一些算法题或者对素数质数问题感兴趣这绝对是一个绕不开的经典。本质上它是一道考察“区间筛法”或者说“二次筛法”的模板题。题目通常会给一个很大的区间[L, R]其中L和R可能非常大比如0 L R 2^31-1但R-L 10^6要求你找出这个区间内所有质数并输出距离最近的一对质数以及距离最远的一对质数。为什么这道题值得单独拿出来说因为它完美地暴露了新手在处理素数问题时最常见的误区直接套用最基础的埃拉托斯特尼筛法埃氏筛。当区间起点L是 0 或者 1终点R是 10^9 时你开一个 10^9 大小的布尔数组试试内存直接爆炸。这道题的精髓也是它作为“模板题”的价值就在于教会我们如何在有限的内存和时间内筛选出一个“局部”但“范围极大”的区间内的素数。它不仅是C竞赛中的常客其背后“化整为零”、“映射偏移”的思想在解决大规模数据过滤、内存敏感型计算问题时有着极强的借鉴意义。今天我们就来彻底拆解这道题不仅给出能AC的代码更要讲清楚每一个细节背后的“为什么”以及我踩过的那些坑。2. 核心思路与算法选型为什么必须是“区间筛法”2.1 传统筛法的局限性分析遇到素数问题我们的第一反应往往是埃氏筛或者欧拉筛线性筛。它们的原理这里简单回顾一下埃氏筛从2开始标记每个质数的倍数为合数欧拉筛则通过“最小质因子”保证每个合数只被标记一次效率更高。它们的代码模板小巧玲珑对付n 10^7量级的数据游刃有余。但是“质数距离”这道题给出了一个经典的限制R - L 10^6但L和R本身可以接近21亿2^31-1。这意味着我们需要关注的区间长度是有限的百万级但区间在数轴上的位置是任意的可能非常靠后。如果我们试图用传统筛法筛到R就需要一个大小为R1的bool数组。当R1,000,000,000时这个数组大约需要1GB内存10^9 bytes这显然超出了大多数在线判题系统OJ的内存限制通常为256MB或512MB。此路不通。2.2 区间筛法二次筛法的原理拆解区间筛法巧妙地避开了这个问题。它的核心思想是我们不需要知道从2到R的所有素数我们只需要知道在[L, R]这个区间内的数是否是素数。那么如何判断一个大数是否是素数呢一个关键定理是一个合数n必然有一个不大于√n的质因子。由此我们得到解题路线图先预处理出所有小于等于sqrt(R)的质数。因为R最大约21亿sqrt(R)最大约46340。筛出这个范围内的质数无论是用埃氏筛还是欧拉筛都只需要一个很小的数组约46KB毫无压力。然后我们创建一个大小为(R-L1)的布尔数组is_prime用于标记区间[L, R]内的每个数是否是质数。初始化时假设它们都是质数。接着对于第1步中筛出的每一个质数p我们找到第一个在区间[L, R]内的、且是p的倍数的数。然后从这个数开始每隔p个位置就把is_prime中对应的标记设为false即标记为合数。这一步会筛掉区间[L, R]内所有含有小于等于sqrt(R)的质因子的合数。筛完之后还留在is_prime中标记为true的数就是区间[L, R]内的所有质数。这个过程中最精妙的一点是下标映射。我们的标记数组is_prime[0]对应的是数Lis_prime[1]对应L1以此类推。所以对于一个给定的数xL x R它在数组中的下标是x - L。反之数组下标i对应的数是L i。2.3 算法流程与复杂度分析预处理小素数使用埃氏筛或欧拉筛获取所有小于等于sqrt(MAX_R)的质数存储在vectorint primes中。复杂度为O(sqrt(R) log log sqrt(R))极小。区间标记数组初始化创建vectorbool is_prime(R - L 1, true)。如果L为 0 或 1需要手动将is_prime[0]和/或is_prime[1]设为false因为0和1不是质数。二次筛除遍历primes中的每个质数p。计算第一个大于等于L的p的倍数。公式为start max((long long)p * p, ((L p - 1) / p) * p)。这里有两个细节为什么从p*p开始这是埃氏筛的标准优化小于p*p的p的倍数已经被更小的质数筛过了。((L p - 1) / p) * p是计算大于等于L的最小的p的倍数的技巧等价于ceil((double)L / p) * p但避免了浮点数运算。从start开始每次递增p直到超过R。对于每一个数j将is_prime[j - L]标记为false。收集结果与计算距离遍历is_prime数组将所有标记为true的下标i对应的数L i存入一个列表prime_list。然后遍历这个列表计算相邻质数的差值更新最小距离对和最大距离对。总的时间复杂度主要由步骤3决定。对于每个小质数p它在区间内标记的次数大约为(R-L)/p次。所有p加起来复杂度可近似为O((R-L) log log R)对于R-L 10^6是完全可以接受的。空间复杂度为O(sqrt(R) (R-L))也完全在限制内。3. 关键实现细节与避坑指南理论清晰了但实现起来处处是坑。下面我结合代码把几个最容易出错的地方掰开揉碎讲清楚。3.1 数据类型与溢出第一个拦路虎这是本题最大的坑没有之一。因为L和R最大可达2^31-1在进行乘法、加法运算时int类型极易溢出。// 错误示例直接使用int计算 int p 46349; // 一个大于sqrt(2^31-1)的质数 int start p * p; // p*p 约等于 2.147e9仍在int范围内不已经溢出了 // 实际上p*p 的计算结果在赋值给start前在表达式内就已经以int类型溢出了。 // 正确做法全程使用 long long long long L, R; cin L R; vectorbool is_prime(R - L 1, true); // 在计算 start 时必须将 p 转换为 long long long long start max((long long)p * p, ((L p - 1) / p) * p); for (long long j start; j R; j p) { is_prime[j - L] false; }注意在max函数中(long long)p * p确保了乘法在long long类型下进行。而((L p - 1) / p) * p这个表达式因为L是long long所以整个表达式也是long long类型。务必保证参与区间下标计算的任何中间变量都是long long。3.2 边界处理L1 和 质数p的范围边界1L 可能为 0 或 1题目说L和R在unsigned int范围内但没说L一定大于1。所以初始化is_prime后必须处理if (L 0) { is_prime[0] false; // 0 不是质数 if (R 1) is_prime[1] false; // 1 不是质数 } else if (L 1) { is_prime[0] false; // 当L1时is_prime[0]对应数字1 }边界2预处理质数的范围预处理质数时我们只需要筛到sqrt(R)。但是sqrt(2^31-1)约等于46340.95。我们应该筛到floor(sqrt(R))吗更稳妥的做法是直接筛到50000或者100000这个开销很小。但严格来说只需要筛到sqrt(R)。在代码中我们可以int limit sqrt(R); // 或者为了保险筛一个稍大的固定值如 100000 vectorbool is_small_prime(100000, true); // ... 执行埃氏筛 ... for (int i 2; i limit; i) { if (is_small_prime[i]) primes.push_back(i); }注意sqrt(R)返回值是double需要转换为int。同时要确保limit在预处理数组的范围内。边界3p*p可能溢出即使使用long long当p很大比如接近sqrt(R)且R也很大时p*p可能超过long long能表示的范围吗sqrt(2^31-1)约 46340其平方约 2.147e9远小于long long的最大值约9e18所以在这个特定问题中是安全的。但这是一个好习惯在计算start时优先使用((L p - 1) / p) * p作为起始点仅当p*p大于这个值且小于等于R时才用p*p。我们的max函数已经实现了这个逻辑。3.3 性能优化vectorbool与位压缩vectorbool在C标准中是一个特化版本它通常每个元素只占1个bit而不是1个byte。这可以节省8倍内存对于R-L 10^6只需要约125KB内存非常友好。但是vectorbool的访问和赋值可能比vectorchar慢一点因为涉及位操作。不过在这道题的数据量下差异可以忽略优先考虑内存。一个更清晰的替代方案是使用vectorchar用1表示质数0表示合数。这样代码更直观且访问速度有保证内存占用约1MB也完全可以接受。我个人的偏好是使用vectorchar避免vectorbool可能带来的某些微妙问题比如不能取地址等。// 两种方式 vectorbool is_prime(R - L 1, true); // 省内存 vectorchar is_prime(R - L 1, 1); // 更直观性能稍好3.4 筛除过程的细节实现这是核心循环我们再看一遍for (long long p : primes) { // 确保 p*p 不会溢出 long long本题范围内安全 long long start max(p * p, ((L p - 1) / p) * p); for (long long j start; j R; j p) { is_prime[j - L] 0; // 标记为合数 } }这里有一个极其重要的优化((L p - 1) / p) * p这个计算在L很大而p也很大的时候(L p - 1)有可能溢出long long吗L最大约2e9p最大约5e4相加约2.00005e9远小于long long上限安全。但如果我们把问题推广到L和R是long long全范围这个计算就需要更谨慎可以使用__int128或者先除后乘来避免溢出。对于本题给定的数据范围当前写法是安全的。4. 完整代码实现与逐行解析下面给出一个鲁棒性高、注释详细的AC代码。我选择使用vectorchar和欧拉筛进行预处理。#include iostream #include vector #include cmath #include climits using namespace std; const int MAX_SQRT 100000; // 预处理的范围略大于sqrt(INT_MAX) // 使用欧拉筛预处理所有小于MAX_SQRT的质数 vectorint get_primes(int n) { vectorint primes; vectorbool is_prime(n 1, true); is_prime[0] is_prime[1] false; for (int i 2; i n; i) { if (is_prime[i]) { primes.push_back(i); } for (int j 0; j primes.size() i * primes[j] n; j) { is_prime[i * primes[j]] false; if (i % primes[j] 0) break; // 欧拉筛关键每个合数只被最小质因子筛一次 } } return primes; } int main() { // 预处理小质数筛到足够大的范围 vectorint primes get_primes(MAX_SQRT); long long L, R; while (cin L R) { // 注意题目可能是多组数据输入 // 初始化区间标记数组1表示质数0表示合数 vectorchar is_prime(R - L 1, 1); // 处理L为0或1的边界情况 if (L 0) { is_prime[0] 0; // 0不是质数 if (R 1) is_prime[1] 0; // 1不是质数 } else if (L 1) { is_prime[0] 0; // 当L1时下标0对应数字1 } // 二次筛用预处理的小质数去标记区间内的合数 for (long long p : primes) { if (p * p R) break; // 如果p^2已经大于R那么p的倍数在区间内最多只有一个p本身而p本身不在区间内或已被处理可提前结束 // 计算起始位置第一个大于等于L的p的倍数且至少是p*p long long start max(p * p, ((L p - 1) / p) * p); // 从start开始标记所有p的倍数 for (long long j start; j R; j p) { is_prime[j - L] 0; } } // 收集区间内的所有质数 vectorlong long prime_list; for (long long i 0; i R - L; i) { if (is_prime[i]) { prime_list.push_back(L i); } } // 寻找距离最近和最远的相邻质数对 if (prime_list.size() 2) { cout There are no adjacent primes. endl; } else { long long min_dist LLONG_MAX, max_dist 0; long long min_left 0, min_right 0, max_left 0, max_right 0; for (size_t i 1; i prime_list.size(); i) { long long dist prime_list[i] - prime_list[i - 1]; if (dist min_dist) { min_dist dist; min_left prime_list[i - 1]; min_right prime_list[i]; } if (dist max_dist) { max_dist dist; max_left prime_list[i - 1]; max_right prime_list[i]; } } cout min_left , min_right are closest, max_left , max_right are most distant. endl; } } return 0; }代码关键点解析预处理函数get_primes使用欧拉筛效率是线性的O(n)。虽然埃氏筛O(n log log n)对此题也足够快但欧拉筛是更通用的模板。主循环while (cin L R)这是一个细节题目输入可能包含多组测试数据直到文件结束EOF。代码需要能连续处理。提前终止条件if (p * p R) break;这是一个重要的优化。当质数p的平方已经大于区间上限R时p在区间[L, R]内的倍数最多只有一个即p本身如果p在区间内。而p本身如果是质数我们不应该把它筛掉。实际上对于大于sqrt(R)的质数p如果它落在区间内它本身就是一个质数不会被任何更小的质数筛掉所以我们不需要用它去筛别人因为它的倍数2p, 3p, ...都大于R了。因此可以直接跳出循环。结果输出格式严格按照题目要求输出。注意当区间内质数少于2个时输出There are no adjacent primes.。5. 常见问题与调试心得即使理解了算法实现时还是会遇到各种稀奇古怪的问题。下面是我在多次提交和调试中总结出来的“血泪教训”。5.1 问题一答案错误特别是边界附近症状对于某些特定的L和R输出的质数对明显不对或者漏掉了某些质数。排查思路检查L0或L1的处理这是最常见的错误。忘记处理0和1会导致把0或1当作质数。检查起始点start的计算手动验证几个例子。比如L100, p7第一个大于等于100的7的倍数是105。((1007-1)/7)*7 (106/7)*7 15*7105正确。再比如L7, p7p*p49((77-1)/7)*7 (13/7)*7 1*77max(49, 7)49。这意味着我们从49开始筛跳过了7本身。这是正确的因为7是质数不应该被标记为合数。检查p的范围确保预处理质数时p的范围至少到sqrt(R)。如果R很大但预处理范围不够就会漏筛。检查数据类型和溢出在计算start和循环变量j时是否全部使用了long long在max函数中是否将p显式转换为long long再进行乘法验证小数据用L2, R100这样的小区间测试手动列出所有质数看程序输出是否一致。5.2 问题二运行超时TLE症状程序在规定时间内没有运行完毕。排查思路复杂度分析算法理论复杂度是O((R-L) log log R)对于R-L10^6应该很快。超时很可能是因为低效的实现。检查内层循环对于每个小质数p内层循环for (long long j start; j R; j p)是性能关键。确保start计算正确避免从太小的数开始无效循环。使用break优化如前所述添加if (p * p R) break;可以提前终止外层循环大幅减少不必要的迭代。这是最重要的优化之一。输入输出效率如果题目是多组数据且数据量很大cin/cout可能成为瓶颈。可以尝试使用scanf/printf或者关闭cin与stdio的同步ios::sync_with_stdio(false); cin.tie(nullptr);。避免不必要的容器操作在收集质数列表prime_list时如果区间很大但质数很少vector的push_back操作影响不大。但如果区间内质数密度很高如L很小频繁的push_back可能导致内存重新分配。可以预先reserve一定的空间或者直接在原数组上遍历两遍第一遍数个数第二遍记录。5.3 问题三内存超限MLE症状程序使用的内存超过了限制。排查思路检查数组大小is_prime数组的大小是R-L1当R-L10^6时vectorchar占用约1MBvectorbool约125KB。如果使用了vectorint4字节每个就会占用4MB虽然可能也够但不如前两者节省。检查预处理数组预处理小质数的数组is_small_prime和primes不应该开得过大。筛到50000或100000足够了如果开到1000000就浪费了。是否存在其他大数组检查代码中是否无意中声明了其他大型全局或局部数组。5.4 个人调试心得与技巧单元测试法不要一上来就用大数据测试。先写几个简单的测试用例比如(2,10)、(10,20)、(1,100)手算结果与程序输出对比。可以使用assert语句在代码中嵌入检查点。中间输出调试在筛完之后先输出区间内找到的所有质数看看是否正确。这能快速定位是筛法错了还是后面找距离的代码错了。关注特殊值L0,L1,L2,R很小R-L很小区间内没有质数区间内只有一个质数这些都是容易出错的边界情况要单独测试。数据类型可视化在计算start时可以把L、p、p*p、((Lp-1)/p)*p的值都打印出来观察它们的变化确保逻辑符合预期。性能分析如果怀疑超时可以注释掉输入输出和结果计算部分只跑筛法看看时间。或者在内层循环加一个计数器看看总共标记了多少次是否在合理范围内大约(R-L) * log log R次。6. 算法扩展与变式思考“质数距离”作为区间筛法的模板其思想可以应用到许多变式问题上。6.1 统计区间质数个数如果问题变成“求[L, R]内质数的个数”我们只需要在筛完后遍历is_prime数组计数即可完全不需要保存质数列表。这甚至更简单。6.2 寻找区间内第K小的质数在筛出所有质数并存入prime_list后因为prime_list是有序的遍历is_prime时顺序插入直接访问prime_list[K-1]即可。注意K可能大于prime_list.size()。6.3 区间内质数的其他性质例如求区间内质数的和、求区间内所有质数的乘积模某个数等等。核心都是先通过区间筛法得到质数列表然后再进行相应的计算。关键在于区间筛法帮助我们以可承受的代价获得了这个“局部”的质数集合。6.4 更大范围的推广本题中R-L 10^6是一个很强的约束。如果区间长度更大比如10^7甚至10^8我们的is_prime数组在内存上可能就有压力了10^8个char约100MB。此时可以考虑分段筛将大区间[L, R]分成若干长度为BLOCK的小段每次只处理一小段重复利用小质数primes数组进行筛除。这样内存占用仅为O(BLOCK)但I/O或处理次数会增加。使用位集bitsetC的std::bitset或vectorbool可以进一步压缩内存但bitset大小需要编译期确定不够灵活。vectorbool在极大数组时可能会有性能问题。6.5 与其他数论知识结合区间筛法常常作为子过程嵌入到更复杂的数论问题中。例如求区间内每个数的质因数分解通过记录每个数被哪个质数筛掉、求区间内所有数的欧拉函数值等。其“用小数筛大区间”的思想是一脉相承的。最后这道题给我的最大启示是面对大规模数据时充分利用约束条件这里是R-L较小来设计算法往往能化不可能为可能。死记模板不行必须理解其背后的数论原理合数必有小质因子和工程技巧偏移映射、避免溢出。把这题吃透以后再遇到需要在超大范围内查找局部性质的素数问题你心里就有底了。在实际编码中我强烈建议将区间筛法封装成一个函数比如vectorlong long sieve_segment(long long L, long long R, const vectorint small_primes)这样主逻辑会更清晰也便于调试和复用。
区间筛法实战：解决质数距离问题与大规模素数筛选
1. 项目概述从一道题看筛法的实战价值“质数距离”这名字听起来有点抽象但如果你刷过一些算法题或者对素数质数问题感兴趣这绝对是一个绕不开的经典。本质上它是一道考察“区间筛法”或者说“二次筛法”的模板题。题目通常会给一个很大的区间[L, R]其中L和R可能非常大比如0 L R 2^31-1但R-L 10^6要求你找出这个区间内所有质数并输出距离最近的一对质数以及距离最远的一对质数。为什么这道题值得单独拿出来说因为它完美地暴露了新手在处理素数问题时最常见的误区直接套用最基础的埃拉托斯特尼筛法埃氏筛。当区间起点L是 0 或者 1终点R是 10^9 时你开一个 10^9 大小的布尔数组试试内存直接爆炸。这道题的精髓也是它作为“模板题”的价值就在于教会我们如何在有限的内存和时间内筛选出一个“局部”但“范围极大”的区间内的素数。它不仅是C竞赛中的常客其背后“化整为零”、“映射偏移”的思想在解决大规模数据过滤、内存敏感型计算问题时有着极强的借鉴意义。今天我们就来彻底拆解这道题不仅给出能AC的代码更要讲清楚每一个细节背后的“为什么”以及我踩过的那些坑。2. 核心思路与算法选型为什么必须是“区间筛法”2.1 传统筛法的局限性分析遇到素数问题我们的第一反应往往是埃氏筛或者欧拉筛线性筛。它们的原理这里简单回顾一下埃氏筛从2开始标记每个质数的倍数为合数欧拉筛则通过“最小质因子”保证每个合数只被标记一次效率更高。它们的代码模板小巧玲珑对付n 10^7量级的数据游刃有余。但是“质数距离”这道题给出了一个经典的限制R - L 10^6但L和R本身可以接近21亿2^31-1。这意味着我们需要关注的区间长度是有限的百万级但区间在数轴上的位置是任意的可能非常靠后。如果我们试图用传统筛法筛到R就需要一个大小为R1的bool数组。当R1,000,000,000时这个数组大约需要1GB内存10^9 bytes这显然超出了大多数在线判题系统OJ的内存限制通常为256MB或512MB。此路不通。2.2 区间筛法二次筛法的原理拆解区间筛法巧妙地避开了这个问题。它的核心思想是我们不需要知道从2到R的所有素数我们只需要知道在[L, R]这个区间内的数是否是素数。那么如何判断一个大数是否是素数呢一个关键定理是一个合数n必然有一个不大于√n的质因子。由此我们得到解题路线图先预处理出所有小于等于sqrt(R)的质数。因为R最大约21亿sqrt(R)最大约46340。筛出这个范围内的质数无论是用埃氏筛还是欧拉筛都只需要一个很小的数组约46KB毫无压力。然后我们创建一个大小为(R-L1)的布尔数组is_prime用于标记区间[L, R]内的每个数是否是质数。初始化时假设它们都是质数。接着对于第1步中筛出的每一个质数p我们找到第一个在区间[L, R]内的、且是p的倍数的数。然后从这个数开始每隔p个位置就把is_prime中对应的标记设为false即标记为合数。这一步会筛掉区间[L, R]内所有含有小于等于sqrt(R)的质因子的合数。筛完之后还留在is_prime中标记为true的数就是区间[L, R]内的所有质数。这个过程中最精妙的一点是下标映射。我们的标记数组is_prime[0]对应的是数Lis_prime[1]对应L1以此类推。所以对于一个给定的数xL x R它在数组中的下标是x - L。反之数组下标i对应的数是L i。2.3 算法流程与复杂度分析预处理小素数使用埃氏筛或欧拉筛获取所有小于等于sqrt(MAX_R)的质数存储在vectorint primes中。复杂度为O(sqrt(R) log log sqrt(R))极小。区间标记数组初始化创建vectorbool is_prime(R - L 1, true)。如果L为 0 或 1需要手动将is_prime[0]和/或is_prime[1]设为false因为0和1不是质数。二次筛除遍历primes中的每个质数p。计算第一个大于等于L的p的倍数。公式为start max((long long)p * p, ((L p - 1) / p) * p)。这里有两个细节为什么从p*p开始这是埃氏筛的标准优化小于p*p的p的倍数已经被更小的质数筛过了。((L p - 1) / p) * p是计算大于等于L的最小的p的倍数的技巧等价于ceil((double)L / p) * p但避免了浮点数运算。从start开始每次递增p直到超过R。对于每一个数j将is_prime[j - L]标记为false。收集结果与计算距离遍历is_prime数组将所有标记为true的下标i对应的数L i存入一个列表prime_list。然后遍历这个列表计算相邻质数的差值更新最小距离对和最大距离对。总的时间复杂度主要由步骤3决定。对于每个小质数p它在区间内标记的次数大约为(R-L)/p次。所有p加起来复杂度可近似为O((R-L) log log R)对于R-L 10^6是完全可以接受的。空间复杂度为O(sqrt(R) (R-L))也完全在限制内。3. 关键实现细节与避坑指南理论清晰了但实现起来处处是坑。下面我结合代码把几个最容易出错的地方掰开揉碎讲清楚。3.1 数据类型与溢出第一个拦路虎这是本题最大的坑没有之一。因为L和R最大可达2^31-1在进行乘法、加法运算时int类型极易溢出。// 错误示例直接使用int计算 int p 46349; // 一个大于sqrt(2^31-1)的质数 int start p * p; // p*p 约等于 2.147e9仍在int范围内不已经溢出了 // 实际上p*p 的计算结果在赋值给start前在表达式内就已经以int类型溢出了。 // 正确做法全程使用 long long long long L, R; cin L R; vectorbool is_prime(R - L 1, true); // 在计算 start 时必须将 p 转换为 long long long long start max((long long)p * p, ((L p - 1) / p) * p); for (long long j start; j R; j p) { is_prime[j - L] false; }注意在max函数中(long long)p * p确保了乘法在long long类型下进行。而((L p - 1) / p) * p这个表达式因为L是long long所以整个表达式也是long long类型。务必保证参与区间下标计算的任何中间变量都是long long。3.2 边界处理L1 和 质数p的范围边界1L 可能为 0 或 1题目说L和R在unsigned int范围内但没说L一定大于1。所以初始化is_prime后必须处理if (L 0) { is_prime[0] false; // 0 不是质数 if (R 1) is_prime[1] false; // 1 不是质数 } else if (L 1) { is_prime[0] false; // 当L1时is_prime[0]对应数字1 }边界2预处理质数的范围预处理质数时我们只需要筛到sqrt(R)。但是sqrt(2^31-1)约等于46340.95。我们应该筛到floor(sqrt(R))吗更稳妥的做法是直接筛到50000或者100000这个开销很小。但严格来说只需要筛到sqrt(R)。在代码中我们可以int limit sqrt(R); // 或者为了保险筛一个稍大的固定值如 100000 vectorbool is_small_prime(100000, true); // ... 执行埃氏筛 ... for (int i 2; i limit; i) { if (is_small_prime[i]) primes.push_back(i); }注意sqrt(R)返回值是double需要转换为int。同时要确保limit在预处理数组的范围内。边界3p*p可能溢出即使使用long long当p很大比如接近sqrt(R)且R也很大时p*p可能超过long long能表示的范围吗sqrt(2^31-1)约 46340其平方约 2.147e9远小于long long的最大值约9e18所以在这个特定问题中是安全的。但这是一个好习惯在计算start时优先使用((L p - 1) / p) * p作为起始点仅当p*p大于这个值且小于等于R时才用p*p。我们的max函数已经实现了这个逻辑。3.3 性能优化vectorbool与位压缩vectorbool在C标准中是一个特化版本它通常每个元素只占1个bit而不是1个byte。这可以节省8倍内存对于R-L 10^6只需要约125KB内存非常友好。但是vectorbool的访问和赋值可能比vectorchar慢一点因为涉及位操作。不过在这道题的数据量下差异可以忽略优先考虑内存。一个更清晰的替代方案是使用vectorchar用1表示质数0表示合数。这样代码更直观且访问速度有保证内存占用约1MB也完全可以接受。我个人的偏好是使用vectorchar避免vectorbool可能带来的某些微妙问题比如不能取地址等。// 两种方式 vectorbool is_prime(R - L 1, true); // 省内存 vectorchar is_prime(R - L 1, 1); // 更直观性能稍好3.4 筛除过程的细节实现这是核心循环我们再看一遍for (long long p : primes) { // 确保 p*p 不会溢出 long long本题范围内安全 long long start max(p * p, ((L p - 1) / p) * p); for (long long j start; j R; j p) { is_prime[j - L] 0; // 标记为合数 } }这里有一个极其重要的优化((L p - 1) / p) * p这个计算在L很大而p也很大的时候(L p - 1)有可能溢出long long吗L最大约2e9p最大约5e4相加约2.00005e9远小于long long上限安全。但如果我们把问题推广到L和R是long long全范围这个计算就需要更谨慎可以使用__int128或者先除后乘来避免溢出。对于本题给定的数据范围当前写法是安全的。4. 完整代码实现与逐行解析下面给出一个鲁棒性高、注释详细的AC代码。我选择使用vectorchar和欧拉筛进行预处理。#include iostream #include vector #include cmath #include climits using namespace std; const int MAX_SQRT 100000; // 预处理的范围略大于sqrt(INT_MAX) // 使用欧拉筛预处理所有小于MAX_SQRT的质数 vectorint get_primes(int n) { vectorint primes; vectorbool is_prime(n 1, true); is_prime[0] is_prime[1] false; for (int i 2; i n; i) { if (is_prime[i]) { primes.push_back(i); } for (int j 0; j primes.size() i * primes[j] n; j) { is_prime[i * primes[j]] false; if (i % primes[j] 0) break; // 欧拉筛关键每个合数只被最小质因子筛一次 } } return primes; } int main() { // 预处理小质数筛到足够大的范围 vectorint primes get_primes(MAX_SQRT); long long L, R; while (cin L R) { // 注意题目可能是多组数据输入 // 初始化区间标记数组1表示质数0表示合数 vectorchar is_prime(R - L 1, 1); // 处理L为0或1的边界情况 if (L 0) { is_prime[0] 0; // 0不是质数 if (R 1) is_prime[1] 0; // 1不是质数 } else if (L 1) { is_prime[0] 0; // 当L1时下标0对应数字1 } // 二次筛用预处理的小质数去标记区间内的合数 for (long long p : primes) { if (p * p R) break; // 如果p^2已经大于R那么p的倍数在区间内最多只有一个p本身而p本身不在区间内或已被处理可提前结束 // 计算起始位置第一个大于等于L的p的倍数且至少是p*p long long start max(p * p, ((L p - 1) / p) * p); // 从start开始标记所有p的倍数 for (long long j start; j R; j p) { is_prime[j - L] 0; } } // 收集区间内的所有质数 vectorlong long prime_list; for (long long i 0; i R - L; i) { if (is_prime[i]) { prime_list.push_back(L i); } } // 寻找距离最近和最远的相邻质数对 if (prime_list.size() 2) { cout There are no adjacent primes. endl; } else { long long min_dist LLONG_MAX, max_dist 0; long long min_left 0, min_right 0, max_left 0, max_right 0; for (size_t i 1; i prime_list.size(); i) { long long dist prime_list[i] - prime_list[i - 1]; if (dist min_dist) { min_dist dist; min_left prime_list[i - 1]; min_right prime_list[i]; } if (dist max_dist) { max_dist dist; max_left prime_list[i - 1]; max_right prime_list[i]; } } cout min_left , min_right are closest, max_left , max_right are most distant. endl; } } return 0; }代码关键点解析预处理函数get_primes使用欧拉筛效率是线性的O(n)。虽然埃氏筛O(n log log n)对此题也足够快但欧拉筛是更通用的模板。主循环while (cin L R)这是一个细节题目输入可能包含多组测试数据直到文件结束EOF。代码需要能连续处理。提前终止条件if (p * p R) break;这是一个重要的优化。当质数p的平方已经大于区间上限R时p在区间[L, R]内的倍数最多只有一个即p本身如果p在区间内。而p本身如果是质数我们不应该把它筛掉。实际上对于大于sqrt(R)的质数p如果它落在区间内它本身就是一个质数不会被任何更小的质数筛掉所以我们不需要用它去筛别人因为它的倍数2p, 3p, ...都大于R了。因此可以直接跳出循环。结果输出格式严格按照题目要求输出。注意当区间内质数少于2个时输出There are no adjacent primes.。5. 常见问题与调试心得即使理解了算法实现时还是会遇到各种稀奇古怪的问题。下面是我在多次提交和调试中总结出来的“血泪教训”。5.1 问题一答案错误特别是边界附近症状对于某些特定的L和R输出的质数对明显不对或者漏掉了某些质数。排查思路检查L0或L1的处理这是最常见的错误。忘记处理0和1会导致把0或1当作质数。检查起始点start的计算手动验证几个例子。比如L100, p7第一个大于等于100的7的倍数是105。((1007-1)/7)*7 (106/7)*7 15*7105正确。再比如L7, p7p*p49((77-1)/7)*7 (13/7)*7 1*77max(49, 7)49。这意味着我们从49开始筛跳过了7本身。这是正确的因为7是质数不应该被标记为合数。检查p的范围确保预处理质数时p的范围至少到sqrt(R)。如果R很大但预处理范围不够就会漏筛。检查数据类型和溢出在计算start和循环变量j时是否全部使用了long long在max函数中是否将p显式转换为long long再进行乘法验证小数据用L2, R100这样的小区间测试手动列出所有质数看程序输出是否一致。5.2 问题二运行超时TLE症状程序在规定时间内没有运行完毕。排查思路复杂度分析算法理论复杂度是O((R-L) log log R)对于R-L10^6应该很快。超时很可能是因为低效的实现。检查内层循环对于每个小质数p内层循环for (long long j start; j R; j p)是性能关键。确保start计算正确避免从太小的数开始无效循环。使用break优化如前所述添加if (p * p R) break;可以提前终止外层循环大幅减少不必要的迭代。这是最重要的优化之一。输入输出效率如果题目是多组数据且数据量很大cin/cout可能成为瓶颈。可以尝试使用scanf/printf或者关闭cin与stdio的同步ios::sync_with_stdio(false); cin.tie(nullptr);。避免不必要的容器操作在收集质数列表prime_list时如果区间很大但质数很少vector的push_back操作影响不大。但如果区间内质数密度很高如L很小频繁的push_back可能导致内存重新分配。可以预先reserve一定的空间或者直接在原数组上遍历两遍第一遍数个数第二遍记录。5.3 问题三内存超限MLE症状程序使用的内存超过了限制。排查思路检查数组大小is_prime数组的大小是R-L1当R-L10^6时vectorchar占用约1MBvectorbool约125KB。如果使用了vectorint4字节每个就会占用4MB虽然可能也够但不如前两者节省。检查预处理数组预处理小质数的数组is_small_prime和primes不应该开得过大。筛到50000或100000足够了如果开到1000000就浪费了。是否存在其他大数组检查代码中是否无意中声明了其他大型全局或局部数组。5.4 个人调试心得与技巧单元测试法不要一上来就用大数据测试。先写几个简单的测试用例比如(2,10)、(10,20)、(1,100)手算结果与程序输出对比。可以使用assert语句在代码中嵌入检查点。中间输出调试在筛完之后先输出区间内找到的所有质数看看是否正确。这能快速定位是筛法错了还是后面找距离的代码错了。关注特殊值L0,L1,L2,R很小R-L很小区间内没有质数区间内只有一个质数这些都是容易出错的边界情况要单独测试。数据类型可视化在计算start时可以把L、p、p*p、((Lp-1)/p)*p的值都打印出来观察它们的变化确保逻辑符合预期。性能分析如果怀疑超时可以注释掉输入输出和结果计算部分只跑筛法看看时间。或者在内层循环加一个计数器看看总共标记了多少次是否在合理范围内大约(R-L) * log log R次。6. 算法扩展与变式思考“质数距离”作为区间筛法的模板其思想可以应用到许多变式问题上。6.1 统计区间质数个数如果问题变成“求[L, R]内质数的个数”我们只需要在筛完后遍历is_prime数组计数即可完全不需要保存质数列表。这甚至更简单。6.2 寻找区间内第K小的质数在筛出所有质数并存入prime_list后因为prime_list是有序的遍历is_prime时顺序插入直接访问prime_list[K-1]即可。注意K可能大于prime_list.size()。6.3 区间内质数的其他性质例如求区间内质数的和、求区间内所有质数的乘积模某个数等等。核心都是先通过区间筛法得到质数列表然后再进行相应的计算。关键在于区间筛法帮助我们以可承受的代价获得了这个“局部”的质数集合。6.4 更大范围的推广本题中R-L 10^6是一个很强的约束。如果区间长度更大比如10^7甚至10^8我们的is_prime数组在内存上可能就有压力了10^8个char约100MB。此时可以考虑分段筛将大区间[L, R]分成若干长度为BLOCK的小段每次只处理一小段重复利用小质数primes数组进行筛除。这样内存占用仅为O(BLOCK)但I/O或处理次数会增加。使用位集bitsetC的std::bitset或vectorbool可以进一步压缩内存但bitset大小需要编译期确定不够灵活。vectorbool在极大数组时可能会有性能问题。6.5 与其他数论知识结合区间筛法常常作为子过程嵌入到更复杂的数论问题中。例如求区间内每个数的质因数分解通过记录每个数被哪个质数筛掉、求区间内所有数的欧拉函数值等。其“用小数筛大区间”的思想是一脉相承的。最后这道题给我的最大启示是面对大规模数据时充分利用约束条件这里是R-L较小来设计算法往往能化不可能为可能。死记模板不行必须理解其背后的数论原理合数必有小质因子和工程技巧偏移映射、避免溢出。把这题吃透以后再遇到需要在超大范围内查找局部性质的素数问题你心里就有底了。在实际编码中我强烈建议将区间筛法封装成一个函数比如vectorlong long sieve_segment(long long L, long long R, const vectorint small_primes)这样主逻辑会更清晰也便于调试和复用。
