C++ 素数对（孪生素数）筛选算法实现

好的，我们来解决这个问题。这是一个典型的素数筛选与配对问题。 ## 🔍 问题分析 我们需要找出所有满足以下条件的素数对 `(p, p+2)`： - `p` 和 `p+2` 都是素数 - 两个数都 ≤ x 例如，当 `x = 20` 时，素数对有：(3,5)、(5,7)、(11,13)、(17,19)。 高效的做法是： 1. 使用**埃拉托斯特尼筛法**（Sieve of Eratosthenes）生成所有 ≤ x 的素数。 2. 遍历筛选后的素数，检查当前素数 `p` 和 `p+2` 是否都是素数，且 `p+2 ≤ x`。 3. 输出所有符合条件的素数对。 ## 💻 C++ 代码实现 ```cpp #include <iostream> #include <vector> using namespace std; // 埃拉托斯特尼筛法，返回布尔数组，isPrime[i] = true 表示 i 是素数 vector<bool> sieve(int n) { vector<bool> isPrime(n + 1, true); isPrime[0] = isPrime[1] = false; for (int i = 2; i * i <= n; ++i) { if (isPrime[i]) { for (int j = i * i; j <= n; j += i) { isPrime[j] = false; } } } return isPrime; } int main() { int x; cout << "请输入 x 的值: "; cin >> x; vector<bool> isPrime = sieve(x); cout << "小于等于 " << x << " 的所有素数对为:" << endl; for (int p = 2; p <= x - 2; ++p) { if (isPrime[p] && isPrime[p + 2]) { cout << "(" << p << ", " << p + 2 << ")" << endl; } } return 0; } ``` ## 🧪 示例运行 **输入：** ``` 请输入 x 的值: 30 ``` **输出：** ``` 小于等于 30 的所有素数对为: (3, 5) (5, 7) (11, 13) (17, 19) (29, 31) ``` ## ⚙️ 关键点说明 - 筛法时间复杂度为 O(n log log n)，适合处理较大的 x 值（如 10^6 级别）。 - 检查 `p + 2 ≤ x` 的条件直接在循环中通过 `p <= x - 2` 保证，避免越界。 - 输出格式清晰，便于直接核对。 ######[AI问答 | 610点数解答 | 2026-06-05 20:20:40]