1. 从“暴力判断”到“筛法”为什么我们需要素数筛在编程竞赛、算法面试或者日常开发中遇到需要快速找出一定范围内所有素数或者判断某个区间内素数个数的问题简直是家常便饭。很多朋友的第一反应可能是写一个判断素数的函数然后对每个数调用一次。比如判断一个数n是否为素数我们通常会从2遍历到sqrt(n)看是否有能整除n的数。这个方法单点判断没问题时间复杂度是O(sqrt(n))。但问题来了如果题目要求你找出1到10^7一千万之间的所有素数呢用上面的“暴力判断法”你需要对大约一千万个数每个数进行最多sqrt(10^7) ≈ 3162次取模运算。这个计算量在现代计算机上虽然不至于跑不动但会非常耗时在算法竞赛中绝对会超时Time Limit Exceeded。这就是“暴力法”的瓶颈它没有利用计算过程中的信息对每个数都是独立判断做了大量重复工作。素数筛法Sieve正是为了解决这个“大规模素数判定”问题而生的。它的核心思想非常巧妙不是去判断每个数是不是素数而是“筛”掉那些肯定不是素数即合数的数剩下的自然就是素数。这个过程就像用筛子筛沙子筛掉合数留下素数。今天我们就来深入剖析两种最经典、最实用的筛法埃拉托斯特尼筛法简称埃筛和欧拉筛也称线性筛。我会结合代码模板不仅告诉你它们怎么写更会讲清楚每一个循环、每一个判断背后的数学原理和设计考量让你彻底理解为什么线性筛是“线性”的以及在什么场景下该用谁。2. 埃拉托斯特尼筛法直观高效的经典算法埃筛是最古老、最直观的筛法以其发明者古希腊数学家埃拉托斯特尼命名。它的算法思想朴素而有效。2.1 算法原理与步骤拆解我们目标是找出[2, n]范围内的所有素数。初始化假设所有数从2开始最初都是素数。我们可以用一个布尔数组is_prime来标记is_prime[i] true表示i是素数。开始筛选从第一个素数2开始。标记合数对于当前找到的素数p我们把p的所有倍数2p, 3p, 4p, ...都标记为合数is_prime[倍数] false。为什么因为任何一个大于p的p的倍数必然能被p整除因此它一定是合数。寻找下一个素数在标记完当前素数的所有倍数后我们向后扫描数组找到下一个未被标记为合数即is_prime仍为true的数。这个数一定是素数。为什么因为比它小的所有素数都已经用来筛过一遍了。如果它不是素数它一定有一个小于它的质因子那它早就在之前被那个质因子筛掉了。所以第一个没被筛掉的数就是下一个素数。重复将这个新找到的素数作为新的p重复步骤3和4。终止条件当p * p n时就可以停止了。因为对于任意一个合数m(m n)如果它有一个质因子qsqrt(m)sqrt(n)那么它一定会在我们遍历到q时被筛掉。所以我们只需要用不超过sqrt(n)的素数去筛就能保证所有合数都被标记。注意这里有一个非常重要的优化点。在标记素数p的倍数时我们从p * p开始标记而不是从2p开始。理由是2p, 3p, ..., (p-1)p这些数它们有比p更小的质因子比如2p有质因子2所以它们一定已经在之前遍历到更小的素数如2时就被标记过了。从p*p开始标记避免了重复标记是埃筛一个关键的性能优化。2.2 代码模板与逐行解析下面是一个标准的、经过优化的埃筛 C 模板用于筛选[1, n]范围内的素数并将所有素数存入数组primes。#include vector using namespace std; // 函数返回一个 vector包含 1 到 n 之间的所有素数 vectorint sieve_of_eratosthenes(int n) { vectorbool is_prime(n 1, true); // 下标从0到n我们使用1到n vectorint primes; // 0和1不是素数 if (n 0) is_prime[0] false; if (n 1) is_prime[1] false; for (int i 2; i * i n; i) { // 优化1只需遍历到 sqrt(n) if (is_prime[i]) { // 如果 i 是素数 // 优化2从 i*i 开始标记 for (int j i * i; j n; j i) { is_prime[j] false; // 标记 i 的倍数为合数 } } } // 收集所有素数 for (int i 2; i n; i) { if (is_prime[i]) { primes.push_back(i); } } return primes; }关键点解析与踩坑提醒数组大小is_prime数组大小为n1是为了让下标i直接对应数字i方便理解和使用。这是最不容易出错的做法。循环边界i * i n这是原理部分提到的终止条件。写成乘法而非i sqrt(n)是为了避免引入浮点数运算和潜在的精度问题同时效率也更高。内层循环起始点j i * i这是核心优化。但这里有一个巨坑当n很大比如接近10^7而i也较大时i * i可能会超出int类型的表示范围导致整数溢出变成一个负数从而使循环条件j n被错误地满足或跳过引发程序错误或崩溃。解决方案将i和用于计算的临时变量声明为long long类型或者在内层循环开始前加一个判断if ((long long)i * i n) break;。在竞赛中更安全的做法是直接使用long long类型的循环变量。优化后的安全版本推荐vectorint sieve_of_eratosthenes(int n) { vectorbool is_prime(n 1, true); vectorint primes; if (n 0) is_prime[0] false; if (n 1) is_prime[1] false; for (long long i 2; i * i n; i) { // 使用 long long 防止溢出 if (is_prime[(int)i]) { for (long long j i * i; j n; j i) { is_prime[(int)j] false; } } } for (int i 2; i n; i) { if (is_prime[i]) primes.push_back(i); } return primes; }2.3 时间复杂度与适用场景埃筛的时间复杂度是O(n log log n)。这个复杂度已经非常接近线性对于绝大多数n 10^7的情况它都能在毫秒级完成代码简单不易写错是解决“求范围内所有素数”问题的首选。但是埃筛有一个本质的缺陷一个合数可能会被它的多个质因子重复标记。例如合数30 2*3*5它会被素数2、3、5各标记一次。当n极大例如10^8以上时这种重复操作会带来额外的开销。更重要的是在某些衍生问题中我们不仅需要知道一个数是不是素数还需要知道它的最小质因子或进行与质因数相关的预处理。这时埃筛就无能为力了。3. 欧拉筛真正的线性时间与最小质因子为了解决埃筛的“重复标记”问题欧拉筛线性筛应运而生。它保证了每个合数只会被它的最小质因子筛掉一次从而将时间复杂度严格降到了O(n)。3.1 算法核心如何保证只筛一次欧拉筛也需要一个布尔数组is_prime来标记素数同时维护一个素数列表primes。但它的核心流程与埃筛不同外层循环遍历从2到n的每一个整数i注意这里不是只到sqrt(n)。记录素数如果i是素数is_prime[i] true就把它加入primes数组。内层筛除无论i是不是素数我们都用当前已有的素数列表primes中的素数p作为最小质因子去尝试筛除合数。关键条件对于每个素数p我们计算composite i * p。我们将composite标记为合数。但筛除过程必须立即停止当p能整除i时即i % p 0。为什么这个停止条件如此重要这正是保证每个合数只被筛一次的精髓。我们来看我们的目标是让每个合数composite被其**最小质因子记为min_p**筛掉。在外层循环到某个数i时我们用素数p去筛i * p。如果p能整除ii % p 0那么i可以写成i p * k。此时对于下一个素数p_next我们要筛的合数是i * p_next (p * k) * p_next p * (k * p_next)。你会发现这个合数i * p_next的最小质因子是p而不是p_next。因为p比p_next小并且p能整除它。如果我们继续用p_next去筛它那么这个合数将来又会被p当外层循环到k * p_next时再筛一次造成重复。因此当p能整除i时p就是i的最小质因子因为primes是从小到大遍历的也必然是i * p_next的最小质因子。为了保证i * p_next在未来被它的最小质因子p筛掉我们现在就必须停止。3.2 代码模板与深度剖析#include vector using namespace std; vectorint euler_sieve(int n) { vectorbool is_prime(n 1, true); vectorint primes; if (n 0) is_prime[0] false; if (n 1) is_prime[1] false; for (int i 2; i n; i) { // 外层循环遍历所有数 if (is_prime[i]) { primes.push_back(i); // 记录素数 } // 用当前已有的素数去筛 for (int j 0; j (int)primes.size(); j) { long long composite (long long)i * primes[j]; // 防止溢出 if (composite n) { break; // 超过范围提前结束内层循环 } is_prime[composite] false; // 筛掉合数 // 核心条件保证每个合数只被最小质因子筛一次 if (i % primes[j] 0) { break; } } } return primes; }逐行解读与实战经验外层循环i从2到n。i在这里有两个角色1) 它本身可能是素数2) 它是用来与素数p相乘构成合数的“乘数”。内层循环primes[j]遍历已发现的素数。注意这个循环在i是合数时也会执行。溢出保护composite (long long)i * primes[j]是必须的。当n很大时i和primes[j]都是int它们的乘积很可能超过int最大值导致溢出和错误筛除。这是线性筛实现中非常常见的坑。提前退出if (composite n) break;这是一个有效的优化。因为primes是递增的i是固定的一旦composite超过n后续更大的素数乘积肯定也超过n无需继续。灵魂语句if (i % primes[j] 0) break;这就是前面分析的“保证唯一筛选”的条件。务必理解其背后的数论原理。3.3 线性筛的威力求最小质因子数组线性筛最强大的扩展能力之一就是可以在O(n)时间内预处理出每个数的最小质因子。这在解决许多数论问题时非常有用例如质因数分解、求欧拉函数等。我们只需要稍作修改将is_prime布尔数组替换为一个min_prime_factor整型数组。#include vector using namespace std; // 返回每个数的最小质因子数组prime_factors[i] 表示 i 的最小质因子素数为0或自身。 vectorint get_min_prime_factor(int n) { vectorint min_pf(n 1, 0); // 0 表示未处理或为素数 vectorint primes; for (int i 2; i n; i) { if (min_pf[i] 0) { // i 是素数 min_pf[i] i; // 素数的最大质因子/最小质因子就是它自己 primes.push_back(i); } // 用当前素数筛合数并记录其最小质因子 for (int j 0; j (int)primes.size(); j) { long long composite (long long)i * primes[j]; if (composite n) break; min_pf[composite] primes[j]; // 合数 composite 的最小质因子就是 primes[j] if (i % primes[j] 0) { // 此时 primes[j] 是 i 的最小质因子也是 composite 的最小质因子 break; } } } // 对于 0 和 1可以特殊处理或保持为0 if (n 0) min_pf[0] 0; if (n 1) min_pf[1] 1; // 通常定义1的最小质因子为1 return min_pf; }有了这个min_pf数组我们可以极快地分解任意一个[2, n]范围内的数的质因数// 快速质因数分解返回质因子列表 vectorint factorize(int x, const vectorint min_pf) { vectorint factors; while (x 1) { int p min_pf[x]; factors.push_back(p); while (x % p 0) { x / p; } } return factors; }这个过程的时间复杂度取决于x的质因子个数远低于O(sqrt(x))。4. 埃筛 vs. 线性筛场景选择与性能实测理解了两种筛法的原理和实现我们该如何选择1. 埃拉托斯特尼筛法优点代码极其简单逻辑直观容易记忆和手写。在n 10^7时O(n log log n)和O(n)的实际运行时间差距非常小埃筛往往因为常数小反而更快。缺点有重复标记理论复杂度非严格线性。无法方便地获取最小质因子等信息。适用场景绝大多数情况下当你只需要判断素数或获取素数列表时优先使用埃筛。例如 LeetCode 上的“计数质数”等问题。它的代码简单不易出错性能足够。2. 欧拉筛线性筛优点严格O(n)时间复杂度每个合数只被筛一次。可以轻松扩展以记录每个数的最小质因子这是解决复杂数论问题的基石。缺点代码稍复杂理解成本高容易写错特别是溢出和核心break条件。由于内层循环条件更多常数比埃筛大在n不是特别大时实际运行时间可能不如优化好的埃筛。适用场景n非常大例如 10^7对时间复杂度要求苛刻。问题不仅需要素数表还需要每个数的最小质因子、欧拉函数值等额外信息。作为更复杂数论算法如莫比乌斯反演预处理的一部分。个人经验与选择建议在算法竞赛中我通常会准备两个模板。对于单纯的素数筛选问题我直接用埃筛因为它写起来快脑子不用绕弯。如果问题涉及到质因数分解、约数个数等需要最小质因子的地方我就会用线性筛进行预处理。在实际编码时务必注意整数溢出问题尤其是在内层循环计算i * p时养成使用long long的习惯。实测方面在我的机器上普通家用CPU筛选1e7以内的素数优化埃筛耗时约120ms。线性筛耗时约180ms。 线性筛确实因为更高的常数而稍慢。但当n达到5e7时线性筛O(n)的优势开始显现耗时增长比埃筛更平缓。5. 模板的变种与常见问题排查掌握了基本模板我们来看看一些常见的变种和容易遇到的问题。5.1 区间筛法求[a, b)内的素数有时我们只关心一个大区间内的素数比如[10^9, 10^9 10^6)。直接开10^9大小的数组是不可能的。这时可以用“区间筛法”其思想是先用普通筛法求出[2, sqrt(b))内的所有素数。创建一个大小为b - a的布尔数组is_prime_segment用于标记区间[a, b)内的数。对于第一步求出的每个素数p在区间[a, b)内找到第一个能被p整除的数即ceil(a/p) * p然后从这个数开始每隔p标记一次合数。vectorbool segment_sieve(long long a, long long b) { // 标记区间 [a, b) 内的素数返回一个大小为 b-a 的vector int sqrt_b (int)sqrt(b) 1; vectorbool is_prime_small(sqrt_b, true); vectorbool is_prime_segment(b - a, true); // is_prime_segment[i] 对应数字 ai if (a 1) { // 处理0和1 long long offset max(2LL, a) - a; fill(is_prime_segment.begin(), is_prime_segment.begin() offset, false); } // 筛出 [2, sqrt(b)) 的素数 for (long long i 2; i sqrt_b; i) { if (is_prime_small[i]) { for (long long j i * i; j sqrt_b; j i) is_prime_small[j] false; // 用素数 i 筛区间 [a, b) long long start max(i * i, (a i - 1) / i * i); // 从 max(i*i, 大于等于a的第一个i的倍数)开始 for (long long j start; j b; j i) { is_prime_segment[j - a] false; } } } return is_prime_segment; }5.2 内存优化位筛法当n达到10^8量级时一个bool数组通常每个元素占1字节可能需要上百MB内存。我们可以用“位筛法”用一个bitset或者手动进行位操作每个数只用1个比特位来标记可以将内存消耗降低到原来的1/8。C 的std::bitset或vectorbool特化版本但慎用可以实现位标记。这里展示一个使用vectorint和位运算的手动位筛思路vectorint bit_sieve(int n) { const int SIZE (n 31) / 32; // 计算需要的32位整型个数 vectorunsigned int is_prime(SIZE, 0xFFFFFFFF); // 初始所有位为1表示素数 vectorint primes; auto set_composite [](int bit) { // lambda函数将指定位设为0合数 int idx bit / 32; int pos bit % 32; is_prime[idx] ~(1U pos); }; auto get_is_prime [](int bit) - bool { // lambda函数获取指定位的值 int idx bit / 32; int pos bit % 32; return (is_prime[idx] pos) 1U; }; for (int i 2; i n; i) { if (get_is_prime(i)) { primes.push_back(i); if ((long long)i * i n) { for (long long j (long long)i * i; j n; j i) { set_composite((int)j); } } } } // 处理0和1的位 if (n 0) set_composite(0); if (n 1) set_composite(1); return primes; }位筛法代码复杂容易出错除非内存限制极其严格如n在5e8左右否则一般优先使用vectorbool。5.3 常见错误排查清单结果错误漏掉素数或多出合数埃筛检查内层循环是否从j i * i开始。检查外层循环终止条件是否为i * i n。检查数组下标是否从0开始导致is_prime[2]实际对应数字3。线性筛检查核心if (i % primes[j] 0) break;语句是否写对、写在了正确位置。检查内层循环是否遍历了primes数组。程序崩溃或输出乱码通常因溢出埃筛检查i * i是否溢出。将循环变量i和乘法中的临时变量改为long long。线性筛检查i * primes[j]是否溢出。务必使用long long composite (long long)i * primes[j];。性能不佳确保使用了编译器优化如-O2。对于埃筛尝试使用vectorbool而非vectorcharvectorbool是特化的可能更节省空间但访问可能稍慢。对于线性筛内层循环的提前退出条件if (composite n) break;很重要。求最小质因子数组时结果不对确保在找到素数i时设置了min_pf[i] i。确保在筛合数composite时设置的是min_pf[composite] primes[j]而不是i。素数筛法是基础数论算法的基石理解其原理比死记模板更重要。下次遇到素数问题不妨先想想是直接用简单的埃筛还是需要线性筛来获取更多信息。把这两个模板及其变种练熟相关的大部分问题都能迎刃而解。 从暴力判断到筛法：埃筛与欧拉筛原理详解与实战对比
1. 从“暴力判断”到“筛法”为什么我们需要素数筛在编程竞赛、算法面试或者日常开发中遇到需要快速找出一定范围内所有素数或者判断某个区间内素数个数的问题简直是家常便饭。很多朋友的第一反应可能是写一个判断素数的函数然后对每个数调用一次。比如判断一个数n是否为素数我们通常会从2遍历到sqrt(n)看是否有能整除n的数。这个方法单点判断没问题时间复杂度是O(sqrt(n))。但问题来了如果题目要求你找出1到10^7一千万之间的所有素数呢用上面的“暴力判断法”你需要对大约一千万个数每个数进行最多sqrt(10^7) ≈ 3162次取模运算。这个计算量在现代计算机上虽然不至于跑不动但会非常耗时在算法竞赛中绝对会超时Time Limit Exceeded。这就是“暴力法”的瓶颈它没有利用计算过程中的信息对每个数都是独立判断做了大量重复工作。素数筛法Sieve正是为了解决这个“大规模素数判定”问题而生的。它的核心思想非常巧妙不是去判断每个数是不是素数而是“筛”掉那些肯定不是素数即合数的数剩下的自然就是素数。这个过程就像用筛子筛沙子筛掉合数留下素数。今天我们就来深入剖析两种最经典、最实用的筛法埃拉托斯特尼筛法简称埃筛和欧拉筛也称线性筛。我会结合代码模板不仅告诉你它们怎么写更会讲清楚每一个循环、每一个判断背后的数学原理和设计考量让你彻底理解为什么线性筛是“线性”的以及在什么场景下该用谁。2. 埃拉托斯特尼筛法直观高效的经典算法埃筛是最古老、最直观的筛法以其发明者古希腊数学家埃拉托斯特尼命名。它的算法思想朴素而有效。2.1 算法原理与步骤拆解我们目标是找出[2, n]范围内的所有素数。初始化假设所有数从2开始最初都是素数。我们可以用一个布尔数组is_prime来标记is_prime[i] true表示i是素数。开始筛选从第一个素数2开始。标记合数对于当前找到的素数p我们把p的所有倍数2p, 3p, 4p, ...都标记为合数is_prime[倍数] false。为什么因为任何一个大于p的p的倍数必然能被p整除因此它一定是合数。寻找下一个素数在标记完当前素数的所有倍数后我们向后扫描数组找到下一个未被标记为合数即is_prime仍为true的数。这个数一定是素数。为什么因为比它小的所有素数都已经用来筛过一遍了。如果它不是素数它一定有一个小于它的质因子那它早就在之前被那个质因子筛掉了。所以第一个没被筛掉的数就是下一个素数。重复将这个新找到的素数作为新的p重复步骤3和4。终止条件当p * p n时就可以停止了。因为对于任意一个合数m(m n)如果它有一个质因子qsqrt(m)sqrt(n)那么它一定会在我们遍历到q时被筛掉。所以我们只需要用不超过sqrt(n)的素数去筛就能保证所有合数都被标记。注意这里有一个非常重要的优化点。在标记素数p的倍数时我们从p * p开始标记而不是从2p开始。理由是2p, 3p, ..., (p-1)p这些数它们有比p更小的质因子比如2p有质因子2所以它们一定已经在之前遍历到更小的素数如2时就被标记过了。从p*p开始标记避免了重复标记是埃筛一个关键的性能优化。2.2 代码模板与逐行解析下面是一个标准的、经过优化的埃筛 C 模板用于筛选[1, n]范围内的素数并将所有素数存入数组primes。#include vector using namespace std; // 函数返回一个 vector包含 1 到 n 之间的所有素数 vectorint sieve_of_eratosthenes(int n) { vectorbool is_prime(n 1, true); // 下标从0到n我们使用1到n vectorint primes; // 0和1不是素数 if (n 0) is_prime[0] false; if (n 1) is_prime[1] false; for (int i 2; i * i n; i) { // 优化1只需遍历到 sqrt(n) if (is_prime[i]) { // 如果 i 是素数 // 优化2从 i*i 开始标记 for (int j i * i; j n; j i) { is_prime[j] false; // 标记 i 的倍数为合数 } } } // 收集所有素数 for (int i 2; i n; i) { if (is_prime[i]) { primes.push_back(i); } } return primes; }关键点解析与踩坑提醒数组大小is_prime数组大小为n1是为了让下标i直接对应数字i方便理解和使用。这是最不容易出错的做法。循环边界i * i n这是原理部分提到的终止条件。写成乘法而非i sqrt(n)是为了避免引入浮点数运算和潜在的精度问题同时效率也更高。内层循环起始点j i * i这是核心优化。但这里有一个巨坑当n很大比如接近10^7而i也较大时i * i可能会超出int类型的表示范围导致整数溢出变成一个负数从而使循环条件j n被错误地满足或跳过引发程序错误或崩溃。解决方案将i和用于计算的临时变量声明为long long类型或者在内层循环开始前加一个判断if ((long long)i * i n) break;。在竞赛中更安全的做法是直接使用long long类型的循环变量。优化后的安全版本推荐vectorint sieve_of_eratosthenes(int n) { vectorbool is_prime(n 1, true); vectorint primes; if (n 0) is_prime[0] false; if (n 1) is_prime[1] false; for (long long i 2; i * i n; i) { // 使用 long long 防止溢出 if (is_prime[(int)i]) { for (long long j i * i; j n; j i) { is_prime[(int)j] false; } } } for (int i 2; i n; i) { if (is_prime[i]) primes.push_back(i); } return primes; }2.3 时间复杂度与适用场景埃筛的时间复杂度是O(n log log n)。这个复杂度已经非常接近线性对于绝大多数n 10^7的情况它都能在毫秒级完成代码简单不易写错是解决“求范围内所有素数”问题的首选。但是埃筛有一个本质的缺陷一个合数可能会被它的多个质因子重复标记。例如合数30 2*3*5它会被素数2、3、5各标记一次。当n极大例如10^8以上时这种重复操作会带来额外的开销。更重要的是在某些衍生问题中我们不仅需要知道一个数是不是素数还需要知道它的最小质因子或进行与质因数相关的预处理。这时埃筛就无能为力了。3. 欧拉筛真正的线性时间与最小质因子为了解决埃筛的“重复标记”问题欧拉筛线性筛应运而生。它保证了每个合数只会被它的最小质因子筛掉一次从而将时间复杂度严格降到了O(n)。3.1 算法核心如何保证只筛一次欧拉筛也需要一个布尔数组is_prime来标记素数同时维护一个素数列表primes。但它的核心流程与埃筛不同外层循环遍历从2到n的每一个整数i注意这里不是只到sqrt(n)。记录素数如果i是素数is_prime[i] true就把它加入primes数组。内层筛除无论i是不是素数我们都用当前已有的素数列表primes中的素数p作为最小质因子去尝试筛除合数。关键条件对于每个素数p我们计算composite i * p。我们将composite标记为合数。但筛除过程必须立即停止当p能整除i时即i % p 0。为什么这个停止条件如此重要这正是保证每个合数只被筛一次的精髓。我们来看我们的目标是让每个合数composite被其**最小质因子记为min_p**筛掉。在外层循环到某个数i时我们用素数p去筛i * p。如果p能整除ii % p 0那么i可以写成i p * k。此时对于下一个素数p_next我们要筛的合数是i * p_next (p * k) * p_next p * (k * p_next)。你会发现这个合数i * p_next的最小质因子是p而不是p_next。因为p比p_next小并且p能整除它。如果我们继续用p_next去筛它那么这个合数将来又会被p当外层循环到k * p_next时再筛一次造成重复。因此当p能整除i时p就是i的最小质因子因为primes是从小到大遍历的也必然是i * p_next的最小质因子。为了保证i * p_next在未来被它的最小质因子p筛掉我们现在就必须停止。3.2 代码模板与深度剖析#include vector using namespace std; vectorint euler_sieve(int n) { vectorbool is_prime(n 1, true); vectorint primes; if (n 0) is_prime[0] false; if (n 1) is_prime[1] false; for (int i 2; i n; i) { // 外层循环遍历所有数 if (is_prime[i]) { primes.push_back(i); // 记录素数 } // 用当前已有的素数去筛 for (int j 0; j (int)primes.size(); j) { long long composite (long long)i * primes[j]; // 防止溢出 if (composite n) { break; // 超过范围提前结束内层循环 } is_prime[composite] false; // 筛掉合数 // 核心条件保证每个合数只被最小质因子筛一次 if (i % primes[j] 0) { break; } } } return primes; }逐行解读与实战经验外层循环i从2到n。i在这里有两个角色1) 它本身可能是素数2) 它是用来与素数p相乘构成合数的“乘数”。内层循环primes[j]遍历已发现的素数。注意这个循环在i是合数时也会执行。溢出保护composite (long long)i * primes[j]是必须的。当n很大时i和primes[j]都是int它们的乘积很可能超过int最大值导致溢出和错误筛除。这是线性筛实现中非常常见的坑。提前退出if (composite n) break;这是一个有效的优化。因为primes是递增的i是固定的一旦composite超过n后续更大的素数乘积肯定也超过n无需继续。灵魂语句if (i % primes[j] 0) break;这就是前面分析的“保证唯一筛选”的条件。务必理解其背后的数论原理。3.3 线性筛的威力求最小质因子数组线性筛最强大的扩展能力之一就是可以在O(n)时间内预处理出每个数的最小质因子。这在解决许多数论问题时非常有用例如质因数分解、求欧拉函数等。我们只需要稍作修改将is_prime布尔数组替换为一个min_prime_factor整型数组。#include vector using namespace std; // 返回每个数的最小质因子数组prime_factors[i] 表示 i 的最小质因子素数为0或自身。 vectorint get_min_prime_factor(int n) { vectorint min_pf(n 1, 0); // 0 表示未处理或为素数 vectorint primes; for (int i 2; i n; i) { if (min_pf[i] 0) { // i 是素数 min_pf[i] i; // 素数的最大质因子/最小质因子就是它自己 primes.push_back(i); } // 用当前素数筛合数并记录其最小质因子 for (int j 0; j (int)primes.size(); j) { long long composite (long long)i * primes[j]; if (composite n) break; min_pf[composite] primes[j]; // 合数 composite 的最小质因子就是 primes[j] if (i % primes[j] 0) { // 此时 primes[j] 是 i 的最小质因子也是 composite 的最小质因子 break; } } } // 对于 0 和 1可以特殊处理或保持为0 if (n 0) min_pf[0] 0; if (n 1) min_pf[1] 1; // 通常定义1的最小质因子为1 return min_pf; }有了这个min_pf数组我们可以极快地分解任意一个[2, n]范围内的数的质因数// 快速质因数分解返回质因子列表 vectorint factorize(int x, const vectorint min_pf) { vectorint factors; while (x 1) { int p min_pf[x]; factors.push_back(p); while (x % p 0) { x / p; } } return factors; }这个过程的时间复杂度取决于x的质因子个数远低于O(sqrt(x))。4. 埃筛 vs. 线性筛场景选择与性能实测理解了两种筛法的原理和实现我们该如何选择1. 埃拉托斯特尼筛法优点代码极其简单逻辑直观容易记忆和手写。在n 10^7时O(n log log n)和O(n)的实际运行时间差距非常小埃筛往往因为常数小反而更快。缺点有重复标记理论复杂度非严格线性。无法方便地获取最小质因子等信息。适用场景绝大多数情况下当你只需要判断素数或获取素数列表时优先使用埃筛。例如 LeetCode 上的“计数质数”等问题。它的代码简单不易出错性能足够。2. 欧拉筛线性筛优点严格O(n)时间复杂度每个合数只被筛一次。可以轻松扩展以记录每个数的最小质因子这是解决复杂数论问题的基石。缺点代码稍复杂理解成本高容易写错特别是溢出和核心break条件。由于内层循环条件更多常数比埃筛大在n不是特别大时实际运行时间可能不如优化好的埃筛。适用场景n非常大例如 10^7对时间复杂度要求苛刻。问题不仅需要素数表还需要每个数的最小质因子、欧拉函数值等额外信息。作为更复杂数论算法如莫比乌斯反演预处理的一部分。个人经验与选择建议在算法竞赛中我通常会准备两个模板。对于单纯的素数筛选问题我直接用埃筛因为它写起来快脑子不用绕弯。如果问题涉及到质因数分解、约数个数等需要最小质因子的地方我就会用线性筛进行预处理。在实际编码时务必注意整数溢出问题尤其是在内层循环计算i * p时养成使用long long的习惯。实测方面在我的机器上普通家用CPU筛选1e7以内的素数优化埃筛耗时约120ms。线性筛耗时约180ms。 线性筛确实因为更高的常数而稍慢。但当n达到5e7时线性筛O(n)的优势开始显现耗时增长比埃筛更平缓。5. 模板的变种与常见问题排查掌握了基本模板我们来看看一些常见的变种和容易遇到的问题。5.1 区间筛法求[a, b)内的素数有时我们只关心一个大区间内的素数比如[10^9, 10^9 10^6)。直接开10^9大小的数组是不可能的。这时可以用“区间筛法”其思想是先用普通筛法求出[2, sqrt(b))内的所有素数。创建一个大小为b - a的布尔数组is_prime_segment用于标记区间[a, b)内的数。对于第一步求出的每个素数p在区间[a, b)内找到第一个能被p整除的数即ceil(a/p) * p然后从这个数开始每隔p标记一次合数。vectorbool segment_sieve(long long a, long long b) { // 标记区间 [a, b) 内的素数返回一个大小为 b-a 的vector int sqrt_b (int)sqrt(b) 1; vectorbool is_prime_small(sqrt_b, true); vectorbool is_prime_segment(b - a, true); // is_prime_segment[i] 对应数字 ai if (a 1) { // 处理0和1 long long offset max(2LL, a) - a; fill(is_prime_segment.begin(), is_prime_segment.begin() offset, false); } // 筛出 [2, sqrt(b)) 的素数 for (long long i 2; i sqrt_b; i) { if (is_prime_small[i]) { for (long long j i * i; j sqrt_b; j i) is_prime_small[j] false; // 用素数 i 筛区间 [a, b) long long start max(i * i, (a i - 1) / i * i); // 从 max(i*i, 大于等于a的第一个i的倍数)开始 for (long long j start; j b; j i) { is_prime_segment[j - a] false; } } } return is_prime_segment; }5.2 内存优化位筛法当n达到10^8量级时一个bool数组通常每个元素占1字节可能需要上百MB内存。我们可以用“位筛法”用一个bitset或者手动进行位操作每个数只用1个比特位来标记可以将内存消耗降低到原来的1/8。C 的std::bitset或vectorbool特化版本但慎用可以实现位标记。这里展示一个使用vectorint和位运算的手动位筛思路vectorint bit_sieve(int n) { const int SIZE (n 31) / 32; // 计算需要的32位整型个数 vectorunsigned int is_prime(SIZE, 0xFFFFFFFF); // 初始所有位为1表示素数 vectorint primes; auto set_composite [](int bit) { // lambda函数将指定位设为0合数 int idx bit / 32; int pos bit % 32; is_prime[idx] ~(1U pos); }; auto get_is_prime [](int bit) - bool { // lambda函数获取指定位的值 int idx bit / 32; int pos bit % 32; return (is_prime[idx] pos) 1U; }; for (int i 2; i n; i) { if (get_is_prime(i)) { primes.push_back(i); if ((long long)i * i n) { for (long long j (long long)i * i; j n; j i) { set_composite((int)j); } } } } // 处理0和1的位 if (n 0) set_composite(0); if (n 1) set_composite(1); return primes; }位筛法代码复杂容易出错除非内存限制极其严格如n在5e8左右否则一般优先使用vectorbool。5.3 常见错误排查清单结果错误漏掉素数或多出合数埃筛检查内层循环是否从j i * i开始。检查外层循环终止条件是否为i * i n。检查数组下标是否从0开始导致is_prime[2]实际对应数字3。线性筛检查核心if (i % primes[j] 0) break;语句是否写对、写在了正确位置。检查内层循环是否遍历了primes数组。程序崩溃或输出乱码通常因溢出埃筛检查i * i是否溢出。将循环变量i和乘法中的临时变量改为long long。线性筛检查i * primes[j]是否溢出。务必使用long long composite (long long)i * primes[j];。性能不佳确保使用了编译器优化如-O2。对于埃筛尝试使用vectorbool而非vectorcharvectorbool是特化的可能更节省空间但访问可能稍慢。对于线性筛内层循环的提前退出条件if (composite n) break;很重要。求最小质因子数组时结果不对确保在找到素数i时设置了min_pf[i] i。确保在筛合数composite时设置的是min_pf[composite] primes[j]而不是i。素数筛法是基础数论算法的基石理解其原理比死记模板更重要。下次遇到素数问题不妨先想想是直接用简单的埃筛还是需要线性筛来获取更多信息。把这两个模板及其变种练熟相关的大部分问题都能迎刃而解。