从暴力判断到筛法：埃筛与欧拉筛原理详解与实战对比

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]范围内的所有素数。

1. 初始化：假设所有数（从2开始）最初都是素数。我们可以用一个布尔数组is_prime来标记，is_prime[i] = true表示i是素数。
2. 开始筛选：从第一个素数2开始。
3. 标记合数：对于当前找到的素数p，我们把p的所有倍数（2p, 3p, 4p, ...）都标记为合数（is_prime[倍数] = false）。为什么？因为任何一个大于p的p的倍数，必然能被p整除，因此它一定是合数。
4. 寻找下一个素数：在标记完当前素数的所有倍数后，我们向后扫描数组，找到下一个未被标记为合数（即is_prime仍为true）的数。这个数一定是素数。为什么？因为比它小的所有素数，都已经用来筛过一遍了。如果它不是素数，它一定有一个小于它的质因子，那它早就在之前被那个质因子筛掉了。所以，第一个没被筛掉的数，就是下一个素数。
5. 重复：将这个新找到的素数作为新的p，重复步骤3和4。
6. 终止条件：当p * p > n时，就可以停止了。因为对于任意一个合数m(m <= n)，如果它有一个质因子q<=sqrt(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 之间的所有素数 vector<int> sieve_of_eratosthenes(int n) { vector<bool> is_prime(n + 1, true); // 下标从0到n，我们使用1到n vector<int> 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数组大小为n+1，是为了让下标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类型的循环变量。

优化后的安全版本（推荐）：

vector<int> sieve_of_eratosthenes(int n) { vector<bool> is_prime(n + 1, true); vector<int> 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。但它的核心流程与埃筛不同：

1. 外层循环：遍历从2到n的每一个整数i（注意，这里不是只到sqrt(n)）。
2. 记录素数：如果i是素数（is_prime[i] == true），就把它加入primes数组。
3. 内层筛除：无论i是不是素数，我们都用当前已有的素数列表primes中的素数p（作为最小质因子）去尝试筛除合数。
4. 关键条件：对于每个素数p，我们计算composite = i * p。我们将composite标记为合数。但筛除过程必须立即停止，当p能整除i时（即i % p == 0）。

为什么这个停止条件如此重要？这正是保证每个合数只被筛一次的精髓。我们来看：

• 我们的目标是让每个合数composite被其**最小质因子（记为min_p）**筛掉。
• 在外层循环到某个数i时，我们用素数p去筛i * p。
• 如果p能整除i（i % 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; vector<int> euler_sieve(int n) { vector<bool> is_prime(n + 1, true); vector<int> 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或自身。 vector<int> get_min_prime_factor(int n) { vector<int> min_pf(n + 1, 0); // 0 表示未处理或为素数 vector<int> 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]范围内的数的质因数：

// 快速质因数分解，返回质因子列表 vector<int> factorize(int x, const vector<int>& min_pf) { vector<int> 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大小的数组是不可能的。这时可以用“区间筛法”，其思想是：

1. 先用普通筛法求出[2, sqrt(b))内的所有素数。
2. 创建一个大小为b - a的布尔数组is_prime_segment，用于标记区间[a, b)内的数。
3. 对于第一步求出的每个素数p，在区间[a, b)内找到第一个能被p整除的数（即ceil(a/p) * p），然后从这个数开始，每隔p标记一次合数。

vector<bool> segment_sieve(long long a, long long b) { // 标记区间 [a, b) 内的素数，返回一个大小为 b-a 的vector int sqrt_b = (int)sqrt(b) + 1; vector<bool> is_prime_small(sqrt_b, true); vector<bool> is_prime_segment(b - a, true); // is_prime_segment[i] 对应数字 a+i 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或vector<bool>（特化版本，但慎用）可以实现位标记。这里展示一个使用vector<int>和位运算的手动位筛思路：

vector<int> bit_sieve(int n) { const int SIZE = (n + 31) / 32; // 计算需要的32位整型个数 vector<unsigned int> is_prime(SIZE, 0xFFFFFFFF); // 初始所有位为1（表示素数） vector<int> 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左右），否则一般优先使用vector<bool>。

5.3 常见错误排查清单

1. 结果错误，漏掉素数或多出合数：

   • 埃筛：检查内层循环是否从j = i * i开始。检查外层循环终止条件是否为i * i <= n。检查数组下标是否从0开始，导致is_prime[2]实际对应数字3。
   • 线性筛：检查核心if (i % primes[j] == 0) break;语句是否写对、写在了正确位置。检查内层循环是否遍历了primes数组。

2. 程序崩溃或输出乱码（通常因溢出）：

   • 埃筛：检查i * i是否溢出。将循环变量i和乘法中的临时变量改为long long。
   • 线性筛：检查i * primes[j]是否溢出。务必使用long long composite = (long long)i * primes[j];。

3. 性能不佳：

   • 确保使用了编译器优化（如-O2）。
   • 对于埃筛，尝试使用vector<bool>而非vector<char>，vector<bool>是特化的，可能更节省空间，但访问可能稍慢。
   • 对于线性筛，内层循环的提前退出条件if (composite > n) break;很重要。

4. 求最小质因子数组时，结果不对：

   • 确保在找到素数i时，设置了min_pf[i] = i。
   • 确保在筛合数composite时，设置的是min_pf[composite] = primes[j]而不是i。

素数筛法是基础数论算法的基石，理解其原理比死记模板更重要。下次遇到素数问题，不妨先想想，是直接用简单的埃筛，还是需要线性筛来获取更多信息。把这两个模板及其变种练熟，相关的大部分问题都能迎刃而解。