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

以下是使用 C++ 实现找出所有两个数均不大于 `x` 的素数组的代码： ```cpp #include <iostream> using namespace std; // 判断一个数是否为素数 bool isPrime(int num) { if (num <= 1) 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` 函数**：用于判断一个数是否为素数。对于小于等于 1 的数，直接返回 `false`；对于大于 1 的数，从 2 开始到该数的平方根进行遍历，如果能被整除则不是素数，返回 `false`，否则返回 `true`。 2. **`main` 函数**： - 读取输入的整数 `x`。 - 从 3 开始遍历到 `x - 4`，对于每个数 `i`，判断 `i` 和 `i + 4` 是否都为素数，如果是，则输出这对素数组。 ### 复杂度分析： - **时间复杂度**：对于每个数，判断素数的时间复杂度为 $O(\sqrt{n})$，遍历所有可能的数的时间复杂度为 $O(x)$，因此总的时间复杂度为 $O(x\sqrt{x})$。 - **空间复杂度**：只使用了常数级的额外空间，因此空间复杂度为 $O(1)$。 ######[AI问答 | 459点数解答 | 2026-04-25 19:51:56]