找出不大于指定范围的素数组的 C++ 实现

以下是实现找出所有两个数均不大于 `x` 的素数组的 C++ 代码： ```cpp #include <iostream> using namespace std; // 判断一个数是否为素数的函数 bool prime(int n) { if (n < 2) return false; // 0 和 1 不是素数 for (int i = 2; i * i <= n; i++) { if (n % i == 0) return false; // 如果能被 2 到 sqrt(n) 之间的数整除，则不是素数 } return true; } int main() { int x; cin >> x; // 输入范围 x for (int i = 2; i <= x - 4; i++) { if (prime(i) && prime(i + 4)) { // 如果 i 和 i + 4 都是素数 cout << i << " " << i + 4 << endl; // 输出素数组 } } return 0; } ``` ### 代码解释： 1. **`prime` 函数**：该函数用于判断一个数是否为素数。如果一个数小于 2，则不是素数；否则，检查该数是否能被 2 到其平方根之间的数整除，如果能，则不是素数，否则是素数。 2. **`main` 函数**： - 首先，从标准输入读取一个整数 `x`，表示范围。 - 然后，使用一个循环遍历从 2 到 `x - 4` 的所有数 `i`。 - 对于每个 `i`，检查 `i` 和 `i + 4` 是否都是素数，如果是，则输出这对素数组。 ### 复杂度分析： - **时间复杂度**：$O(x\sqrt{x})$，其中 $x$ 是输入的范围。对于每个数，判断其是否为素数的时间复杂度为 $O(\sqrt{n})$，需要遍历 $x$ 个数。 - **空间复杂度**：$O(1)$，只使用了常数级的额外空间。 ######[AI问答 | 506点数解答 | 2026-04-26 18:43:02]