埃拉托斯特尼筛法（埃氏筛）完整解析

一、算法用途

快速找出 2 ~ n 之间的所有素数。

• 暴力判断每个数：O(nn​)
• 埃氏筛：O(nloglogn)，接近线性，极快。

二、核心思想

1. 先假设所有数都是素数。
2. 从最小素数 2 开始，把它的所有倍数标记为合数。
3. 取下一个没被标记的数（一定是素数），继续标记它的倍数。
4. 最后没被标记的，就是素数。

三、完整算法步骤

以筛出 2~n 内素数为例：

1. 初始化建立数组 is_prime[]，长度 n+1，全部设为 true。is_prime[0] = is_prime[1] = false（0、1 不是素数）。

2. 遍历筛选从 i = 2 开始，只遍历到 √n：

   • 如果 is_prime[i] == true，说明 i 是素数。
   • 把 i², i²+i, i²+2i … ≤n 全部标记为 false。

3. 收集结果遍历数组，所有 is_prime[i] == true 的 i 都是素数。

四、关键问题：为什么只需要遍历到 √n？