【模板】埃拉托色尼筛法（埃氏筛）

一、算法简介

在数论与编程竞赛中，求解 $[1,n]$ 范围内的所有质数是常见的基础问题。埃拉托色尼筛法（Sieve of Eratosthenes） 是一种古老而高效的算法，可以在 $O(n\log \log n)$ 的时间复杂度内完成这一任务。

---

二、基本思想

埃氏筛的核心思想是：

对于每一个从小到大的质数 $p$，将其所有的倍数（$2p,3p,4p,\dots$）标记为合数。
最终，所有未被标记的数就是质数。

举例说明：
设 $n=30$，初始认为 $2\sim 30$ 都是质数。
我们从 $2$ 开始，依次把 $4,6,8,\dots$ 标记为合数；
然后处理下一个未被标记的 $3$，再把 $6,9,12,\dots$ 标记为合数；
如此反复，直到 $\sqrt{n}$。

---

三、代码实现

以下是使用 C++ 编写的埃氏筛标准模板

#include<iostream>
#include<vector>
using namespace std;const int N = 1e5 + 10; // 设置一个足够大的常数N，表示数组大小vector<bool> ans(N, true); // 初始化素数表，默认所有数都是素数（true）
vector<int> nums;          // 用于存储最终得到的所有质数// 筛法主函数：获取1到n之间的所有素数
void get(int n)
{ans[0] = ans[1] = false; // 0 和 1 不是质数，直接标记为 false// 使用埃氏筛法，从 2 开始依次判断for (int i = 2; i <= n / i; i++)  // 等价于 i * i <= n{if (ans[i]) // 如果当前数 i 是质数（尚未被筛掉）{// 从 i*i 开始，而不是 2*i：// 因为 i < j < i*i 范围内的 i 倍数，如 2*i, 3*i 等，已被更小的质数筛掉了for (int j = i * i; j <= n; j += i) // 枚举 i 的所有倍数{ans[j] = false; // 将 j 标记为合数}}}// 将所有的质数加入 nums 数组for (int k = 2; k <= n; k++){if (ans[k]){nums.push_back(k);}}
}

主函数调用如下：

int main()
{int n;cin >> n; // 输入要求筛到的最大范围get(n); // 执行筛法for (auto num : nums){cout << num << " "; // 输出所有质数}return 0;
}

---

四、关键优化说明

1. 为什么从 i * i 开始筛？

因为在遍历到质数 $i$ 时，小于 $i$ 的质数已经处理了 $2i,3i,...,(i-1)i$ 的倍数。例如：

• $6=2\times 3$ 会在处理 $2$ 时被筛掉；
• $9=3\times 3$ 会在处理 $3$ 时被筛掉。

因此，从 $i\times i$ 开始可以减少重复标记，提升效率。

2. 循环条件 i <= n / i

等价于 i * i <= n，这种写法可避免整数溢出，建议记住作为一种 防溢出技巧。

---

五、时间与空间复杂度

• 时间复杂度：$O(n\log \log n)$，非常高效
• 空间复杂度：$O(n)$，主要用于布尔数组 ans[]

---

六、样例输入输出

输入：

100

输出：

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

---

七、适用场景与拓展

• 快速判断一个数是否为质数（配合布尔数组）
• 枚举某范围内的所有质数（如用于欧拉函数、积性函数计算）
• 可拓展为线性筛（Euler 筛）以避免重复标记（时间复杂度为 $O(n)$）

---

八、结语

埃拉托色尼筛法是数论的入门利器，是多种算法的基础工具。建议熟练掌握并牢记模板结构。同时要理解从 i * i 开始标记的数学依据，避免盲记公式。