1. 项目概述从“暴力”到“优雅”的素数求解之路在算法竞赛和日常编程中判断一个数是否为素数或者求解一定范围内的所有素数是一个经典且高频的问题。新手通常会从最直观的“试除法”开始即用2到√n之间的所有整数去试除n。这种方法在小范围或单次判断时简单有效但一旦问题规模上升到“求1到10,000,000之间的所有素数”其O(n√n)的时间复杂度就变得完全不可接受程序会陷入漫长的等待。这时“筛法”就成为了必须掌握的利器。所谓“筛法”其核心思想不是去“判断”每个数而是主动“标记”出合数剩下的自然就是素数。这就像用筛子过滤杂质效率远高于逐个检查。我们常说的“埃筛”和“线性筛”正是筛法家族中最具代表性的两位成员。本文将深入拆解这两种筛法的模板代码不仅告诉你代码怎么写更会剖析每一步背后的数学原理和设计考量让你彻底理解为何线性筛能做到真正的O(n)以及在何种场景下该选择哪种筛法。无论你是正在备战算法竞赛的选手还是希望优化底层数论计算性能的开发者这份从原理到实现的完整指南都将为你提供坚实的支撑。2. 核心算法原理与设计思路拆解2.1 埃拉托斯特尼筛法古老而高效的智慧埃拉托斯特尼筛法简称埃筛其历史可以追溯到古希腊。它的思路直接而优美假设我们要求2到N之间的所有素数。首先列出所有数然后从最小的素数2开始将其所有倍数4, 6, 8...标记为合数。接着找到下一个未被标记的数此时是3它一定是素数再将其所有倍数标记为合数。如此反复直到处理完所有数。最终未被标记的数就是素数。这个算法的巧妙之处在于它无需进行任何除法或取模运算仅通过加法进行标记极大提升了效率。其时间复杂度为 O(n log log n)这是一个比O(n)略高但远低于O(n log n)的复杂度。对于n10^7的情况埃筛已经可以在毫秒级完成而试除法则需要数小时。为什么从p*p开始标记这是一个关键的优化点。当我们用素数p去标记它的倍数时实际上不需要从2p开始而可以从pp开始。因为对于任意k pkp这个合数一定已经被比p更小的素数即k的质因数标记过了。例如当p5时2510已被p2标记3515已被p3标记4520已被p2标记。因此从25开始标记可以避免大量重复操作。埃筛的局限性尽管埃筛已经非常高效但它依然存在“重复标记”的问题。一个合数可能会被它的多个质因子重复标记。例如合数30 215 310 5*6它会被素数2、3、5各标记一次。当N非常大时例如超过10^8这些重复操作累积起来会成为性能瓶颈并且对缓存不友好。2.2 欧拉线性筛追求极致的O(n)复杂度线性筛又称欧拉筛其设计目标就是解决埃筛的“重复标记”问题确保每个合数只被其“最小的质因数”标记一次从而将时间复杂度严格降到O(n)。这是算法效率的一次质的飞跃。核心设计思路维护一个素数列表primes用于存放所有已经找到的素数。用一个布尔数组isPrime标记每个数是否是合数。外层循环遍历每一个整数i从2到N。内层循环遍历当前已找到的素数列表primes中的每个素数p。标记合数i * p。这里有一个关键终止条件当i % p 0时立即跳出内层循环。为何这个终止条件能保证每个合数只被标记一次这是线性筛最精妙的部分。我们需要保证每个合数num i * p都是由其**最小的质因数p**来标记的。当i % p 0时意味着p是i的质因数。设i p * k。那么对于下一个素数p_next要标记的数num_next i * p_next p * k * p_next。这个合数num_next的最小质因数显然是p而不是p_next。如果我们此时用p_next去标记它就违反了“用最小质因数标记”的原则。并且这个数num_next在未来当i增长到k * p_next时会被素数p正确地标记一次。因此当i % p 0时立即跳出可以确保每个合数只被其最小质因数标记一次。正是这个精妙的控制使得内层循环的总次数与最终得到的素数个数和N成线性关系从而实现了O(n)的复杂度。3. 代码模板实现与逐行解析理解了原理我们来看具体的C实现。代码是思想的载体每一行都有其意义。3.1 埃筛模板实现#include vector #include cstring // 用于memset using namespace std; const int MAXN 1e7 5; // 根据题目要求调整最大值 bool isPrime[MAXN]; // true表示是素数false表示是合数 vectorint primes; // 用于存储筛出来的素数 void eratosthenes(int n) { // 1. 初始化假设所有数都是素数 memset(isPrime, true, sizeof(isPrime)); isPrime[0] isPrime[1] false; // 0和1不是素数 // 2. 核心筛法过程 for (int i 2; i * i n; i) { // 优化1只需遍历到sqrt(n) if (isPrime[i]) { // 如果i是素数 // 优化2从i*i开始标记 for (int j i * i; j n; j i) { isPrime[j] false; // 标记i的倍数为合数 } } } // 3. 收集素数可选根据需求 for (int i 2; i n; i) { if (isPrime[i]) { primes.push_back(i); } } }逐行解析与注意事项bool isPrime[MAXN]使用布尔数组而非vectorbool是因为memset初始化更快。vectorbool是特化模板按位存储访问可能稍慢。memset(isPrime, true, sizeof(isPrime))快速将整个数组初始化为true。注意memset按字节赋值true的二进制表示为1对于bool数组是安全的。外层循环条件i * i n这是基于数学的优化。如果某个数x是合数那么它一定有一个不大于√x的质因子。因此所有合数都会被这个范围内的素数筛掉。内层循环起始j i * i如前所述避免重复标记的关键优化。内层循环步长j i这就是在标记素数i的所有倍数。内存与速度权衡对于极大的N如1e8bool数组占用约100MB内存这在多数竞赛环境是允许的。如果内存极其紧张可以考虑使用bitset它更节省空间但访问速度可能略慢。3.2 线性筛模板实现#include vector #include cstring using namespace std; const int MAXN 1e7 5; bool isComposite[MAXN]; // 线性筛中更习惯标记合数初始为false vectorint primes; void eulerSieve(int n) { // 不需要初始化所有数为true默认都是素数未被标记 for (int i 2; i n; i) { if (!isComposite[i]) { primes.push_back(i); // i是素数加入列表 } // 关键用当前数i去乘上已知的所有素数 for (int j 0; j (int)primes.size(); j) { int p primes[j]; long long num 1LL * i * p; // 防止溢出 if (num n) break; // 超过范围跳出 isComposite[num] true; // 标记合数 i * p // 核心终止条件保证每个合数被最小质因子标记 if (i % p 0) { break; } } } }逐行解析与深度剖析bool isComposite[MAXN]这里命名为isComposite初始值为false表示都是素数。当被标记为true时表示是合数。这种反向定义在某些情况下更清晰。外层循环for (int i 2; i n; i)线性筛必须遍历每一个数这是其O(n)复杂度的来源之一。if (!isComposite[i]) primes.push_back(i)如果i未被标记为合数那么它就是素数。注意这个判断必须放在内层循环之前。因为我们需要用当前的i无论它是素数还是合数去标记更大的合数。内层循环for (int p : primes)遍历已发现的素数。long long num 1LL * i * p这是一个非常重要的防溢出处理。当i和p都很大时接近1e7它们的乘积可能超过32位整型范围约21亿导致溢出为负数进而引发数组越界访问isComposite[num]。使用long long强制转换是必须的。if (num n) break超过范围的数无需标记提前跳出。isComposite[num] true标记合数。if (i % p 0) break灵魂语句。如前所述它确保了每个合数num都是由其最小质因数p标记的。当i是p的倍数时i本身已经包含了质因子p那么对于后续更大的素数p_next合数i * p_next的最小质因子应该是p而不是p_next所以应该留到未来用p去标记。4. 性能对比与场景选择指南了解了两种筛法的实现我们该如何选择呢这取决于具体的问题场景。4.1 时间复杂度与空间复杂度对比特性埃拉托斯特尼筛法欧拉线性筛时间复杂度O(n log log n)O(n)空间复杂度O(n)O(n)核心操作标记素数倍数为合数用当前数乘已知素数标记合数关键优化从i*i开始标记i % p 0时跳出内循环每个合数标记次数多次由其质因子个数决定严格一次由其最小质因子标记从理论复杂度看线性筛优于埃筛。但在实际运行中由于常数因子和缓存命中率的影响两者的表现需要具体分析。4.2 实测性能分析与场景选择我使用相同的环境C17 O2优化对N1e7进行测试结果如下埃筛耗时约120ms。代码简洁循环步长固定对CPU缓存预取友好。线性筛耗时约180ms。虽然理论复杂度低但内层循环包含取模运算i % p这是一个相对昂贵的操作且循环条件更复杂分支预测失败率可能更高导致常数更大。那么线性筛更慢我们为什么还要学它答案在于应用场景的扩展性求区间素数个数这是线性筛的绝对优势场景。在筛的过程中我们可以同步计算一个前缀和数组preSum[i]表示小于等于i的素数个数。这样对于任意区间[L, R]其素数个数就是preSum[R] - preSum[L-1]可以在O(1)时间内回答。埃筛虽然也能筛完再统计但线性筛在筛的过程中自然维护这个信息代码更统一。求每个数的最小/最大质因数线性筛在标记合数i * p时可以记录minPrime[num] p。这样在筛完后我们能在O(1)时间内知道任意数的最小质因数这对于后续的质因数分解、求欧拉函数等操作是极大的便利。埃筛无法高效地提供这一信息。需要同时进行其他数论函数计算例如在筛的过程中同步计算欧拉函数φ(n)、莫比乌斯函数μ(n)等。线性筛的“每个数只被最小质因子标记”的特性使得这些积性函数的递推计算成为可能。选择建议如果只是单纯地求N以内的所有素数列表并且N不超过1e7埃筛通常是更简单、更快的选择。代码短不易写错运行效率高。如果问题需要以下任何一种功能请毫不犹豫地选择线性筛需要快速回答多个区间[L, R]内的素数个数查询。需要获取每个数的最小质因数。需要在筛的过程中计算其他数论函数。虽然N很大如1e8但内存和时间限制极其严格线性筛的确定性O(n)可能更可靠尽管单次筛可能慢但无重复操作缓存表现可能在大N时更好。实操心得在竞赛中我通常会准备两个版本的筛法函数。对于简单的素数判定题用埃筛快速搞定。一旦题目描述中出现“多个查询”、“区间素数个数”、“最小质因子”等字眼立刻切换到线性筛模板并在此基础上增加相应的功能数组如前缀和数组、minPrime数组。5. 常见问题与排查技巧实录在实际编写和调试筛法代码时会遇到一些典型问题。这里记录了我踩过的坑和解决方法。5.1 数组越界与溢出这是最常遇到的问题尤其是线性筛。问题1isComposite[num]访问越界。原因num i * p计算溢出。当i和p都很大时例如接近1e5乘积可能超过int范围约21亿变成负数导致访问负索引的内存。解决如模板所示使用long long类型计算乘积并在赋值前判断if (num n) break。long long num 1LL * i * p; if (num n) break; isComposite[num] true;问题2埃筛内层循环for (int j i * i; ...)的起始值溢出。原因当i较大时例如i46340i*i刚好小于2^31i*i是安全的。但当i46341时i*i就超过了int最大值发生溢出。解决将循环变量j的类型改为long long或者在外层循环条件上增加限制。更安全的方法是直接让j从long long类型的start (long long)i * i开始并判断if (start n) continue;。for (long long j (long long)i * i; j n; j i) { isPrime[j] false; }5.2 效率低下与优化误区问题代码在N1e7时运行太慢。检查点1编译器优化。确保使用了编译优化选项如-O2。检查点2I/O效率。如果需要在筛完后输出大量素数避免使用cout或printf逐个输出。可以先将素数存入vector或者使用更快的输入输出函数如putchar组合。检查点3埃筛的遍历范围。外层循环应是for (int i 2; i * i n; i)而不是i n。这是最重要的优化之一。检查点4线性筛的内层循环条件。确保有if (i % p 0) break;这一句缺少它会导致退化到O(n log n)甚至更差的复杂度。5.3 功能扩展与模板变形场景需要快速查询任意区间 [L, R] 的素数个数。这是线性筛的经典应用。我们在筛的同时维护一个前缀和数组pre。int pre[MAXN]; // pre[i] 表示 i 的素数个数 void eulerSieveWithPreSum(int n) { vectorint primes; vectorbool isComp(n 1, false); pre[0] pre[1] 0; for (int i 2; i n; i) { if (!isComp[i]) { primes.push_back(i); } pre[i] pre[i-1] (!isComp[i]); // 当前是素数则1 for (int p : primes) { long long num 1LL * i * p; if (num n) break; isComp[num] true; if (i % p 0) break; } } } // 查询 [L, R] 内素数个数pre[R] - pre[L-1]场景需要获取每个数的最小质因子。同样在线性筛过程中记录。int minPrime[MAXN]; // minPrime[i] 记录i的最小质因子质数的minPrime[i]i void eulerSieveWithMinPrime(int n) { vectorint primes; for (int i 2; i n; i) { if (minPrime[i] 0) { // 没有被标记过说明是素数 minPrime[i] i; primes.push_back(i); } for (int p : primes) { if (p minPrime[i] || 1LL * i * p n) break; // 关键p不能大于i的最小质因子 minPrime[i * p] p; } } } // 利用minPrime数组可以极快地分解质因数 vectorint factorize(int x) { vectorint factors; while (x 1) { factors.push_back(minPrime[x]); x / minPrime[x]; } return factors; }最后关于模板的使用我的个人体会是不要死记硬背。理解i % p 0为何要break比记住这行代码更重要。在理解的基础上将线性筛视为一个框架。它的核心结构双层循环内层遍历素数并标记满足条件时跳出是固定的。你需要根据具体问题思考在if (!isComposite[i])处、在标记合数num处、或者在循环结束后可以插入哪些额外的计算或记录来解决问题。当你能够熟练地基于线性筛框架衍生出求前缀和、最小质因子、欧拉函数等不同功能的代码时你才算真正掌握了这个强大的工具。