C++实现找出不大于x的所有素数组

以下是实现该功能的C++代码： ```cpp #include <iostream> using namespace std; // 判断一个数是否为素数 bool isPrime(int num) { if (num < 2) return false; for (int i = 2; i * i <= num; i++) { if (num % i == 0) return false; } return true; } int main() { int x; cin >> x; // 遍历寻找素数组 for (int i = 3; i <= x - 4; i++) { if (isPrime(i) && isPrime(i + 4)) { cout << i << " " << i + 4 << endl; } } return 0; } ``` ### 代码解释 1. **`isPrime` 函数**：用于判断一个数是否为素数。如果该数小于2，则直接返回 `false`；否则，从2开始到该数的平方根进行遍历，如果能被整除，则不是素数，返回 `false`；否则返回 `true`。 2. **`main` 函数**： - 读取输入的整数 `x`。 - 从3开始遍历到 `x - 4`，对于每个数 `i`，判断 `i` 和 `i + 4` 是否都为素数，如果是，则输出这对素数组。 ### 复杂度分析 - **时间复杂度**：$O(x\sqrt{x})$，其中 $x$ 是输入的整数。主要是因为对于每个数都需要调用 `isPrime` 函数，而 `isPrime` 函数的时间复杂度为 $O(\sqrt{num})$。 - **空间复杂度**：$O(1)$，只使用了常数级的额外空间。 ######[AI问答 | 433点数解答 | 2026-05-01 19:58:51]