埃拉托色尼筛法

1. 核心定义

一种简单且历史悠久的算法，用于找出一定范围内（小于等于 $N$）的所有素数。

2. 算法步骤

1. 初始化：列出从 $2$ 到 $N$ 的所有整数。
2. 筛选：
   • 找到列表中最小的未被标记的数 $p$（初始为2），它是一个素数。
   • 标记 $p$ 的所有倍数（$2p,3p,\dots$）为合数（划去）。
   • 找到下一个未被标记的数，重复上述步骤。
3. 终止：当 $p^2>N$ 时停止，剩下的所有未被标记的数即为素数。

3. 性能与特点

• 时间复杂度：$O(N\log \log N)$。非常高效，接近线性。
• 局限性：适用于寻找中小范围内的素数表。对于生成超大素数（如 RSA 密钥生成），通常不使用筛选法，而是使用 素性检测（如 Miller-Rabin，后续章节会学）。

4. 示例 ($N=10$)

• 列表：2, 3, 4, 5, 6, 7, 8, 9, 10
• $p=2$：划去 4, 6, 8, 10。剩余：2, 3, 5, 7, 9
• $p=3$：划去 9。剩余：2, 3, 5, 7
• $3^2\approx 10$ (接近边界)，结束。素数为 $\{2,3,5,7\}$。