筛选法求素数是一种高效求素数的方法，其具体算法如下： 从2开始把连续的整数放入筛中，首先确定筛中第一个数2是素数。并从筛中晒去所有2的倍数（不包括2）；然后从2以后开始查找，找到筛中剩下的第一个数，它也是素数，并从筛中筛去它的所有倍数（不包括本身）。如此反复执行，直到无数可筛为止。这时筛中剩下的就是这一串就是素数。 提示： 可以用一个数组ss作为筛，数组的下标代表连续的整数，若储存的是0时，代表不在筛中，储存的是1时，代表在筛中。如ss[2]=1代表整数2在筛中。   本题中要求输入一个数n，输出2到n中的所有素数。 输入 一行n（300000>n) 输出 2到n的所有素数（c++）

```cpp #include <iostream> using namespace std; const int MAXN = 300000; int ss[MAXN + 1]; int main() { int n; cin >> n; // 初始化筛，所有数都在筛中 for (int i = 2; i <= n; ++i) { ss[i] = 1; } // 筛选素数 for (int i = 2; i * i <= n; ++i) { if (ss[i] == 1) { for (int j = i * i; j <= n; j += i) { ss[j] = 0; } } } // 输出所有素数 for (int i = 2; i <= n; ++i) { if (ss[i] == 1) { cout << i << endl; } } return 0; } ``` 代码解释 1. 筛数组初始化：创建一个大小为`MAXN + 1`的数组`ss`，并将`2`到`n`的元素初始化为`1`，表示这些数都在筛中。 2. 筛选素数：从`2`开始遍历到`sqrt(n)`，如果当前数`i`在筛中（`ss[i] == 1`），则将其倍数（从`i * i`开始）标记为不在筛中（`ss[j] = 0`）。 3. 输出素数：遍历`2`到`n`的所有数，如果该数在筛中（`ss[i] == 1`），则输出该数。 复杂度分析 - 时间复杂度：$O(n log log n)$ - 空间复杂度：$O(n)$ [2026-02-06 20:08:38 | AI问答 | 431点数解答]