如何用筛法求某个区间的素数

筛法是一种高效的查找一定范围内质数的经典算法，常用的有埃拉托斯特尼筛法（Sieve of Eratosthenes）和更高效的段筛法。以下是使用埃拉托斯特尼筛法求解某个区间内的所有素数的基本步骤：

1. **初始化数组**：创建一个长度为目标区间的整数数组，初始值全部设置为 `true`，表示每个数都是潜在的素数。

2. **从最小的质数开始**：从2开始（因为2是最小的质数），将所有2的倍数标记为非素数（即数组元素设为 `false`）。然后找到下一个未被标记的数字3，并将其倍数标记为非素数。

3. **递增过程**：每次迭代时，处理当前未被标记的最大质数，例如3、5、7等，将它的所有倍数都标记为非素数。然后跳到下一个未被标记的数，继续这个过程，直到遍历完当前范围内的所有奇数。

4. **筛选结果**：最后，数组中那些仍然标记为 `true` 的位置就是区间内的素数。这些索引对应的值就是区间内的素数。

举个例子：
假设我们要找区间 [20, 30] 内的素数：
- 初始化数组，所有值为 true: [true, true, ..., true]
- 首先，2的倍数标记为 false: [true, false, ..., true, false, ...]
- 然后处理3，其倍数标记：[true, false, true, false, ..., true, false, false]
- 接着是5，再标记其倍数...
- 最终，我们得到 [20, 23, 29] 作为结果