C++实现素数对查找算法详解及优化方法

## 📝 问题分析 题目要求找出所有小于等于 x 的素数对，即两个素数相差2的组合（如(3,5), (5,7), (11,13)等）。 ## 💻 完整代码实现（C++） ```cpp #include <iostream> #include <vector> using namespace std; // 判断一个数是否为素数 bool isPrime(int n) { if (n < 2) return false; for (int i = 2; i * i <= n; i++) { if (n % i == 0) return false; } return true; } int main() { int x; cout << "请输入x的值: "; cin >> x; cout << "小于等于" << x << "的所有素数对:" << endl; // 遍历所有可能的素数对 for (int i = 2; i <= x - 2; i++) { if (isPrime(i) && isPrime(i + 2)) { cout << "(" << i << ", " << i + 2 << ")" << endl; } } return 0; } ``` ## 🔧 算法步骤说明 1. **素数判断函数** `isPrime(n)`：检查 n 是否为素数。从2到sqrt(n)遍历，若 n 能被任何数整除则不是素数。 2. **主函数逻辑**： - 输入上界 x - 从2遍历到 x-2（因为需要留出相差2的空间） - 对每个数 i，检查 i 和 i+2 是否都是素数 - 若都是素数则输出这对素数对 ## ⚡ 优化版本（使用筛选法） ```cpp #include <iostream> #include <vector> using namespace std; vector<bool> sieveOfEratosthenes(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 = sieveOfEratosthenes(x); cout << "小于等于" << x << "的所有素数对:" << endl; for (int i = 2; i <= x - 2; i++) { if (isPrime[i] && isPrime[i + 2]) { cout << "(" << i << ", " << i + 2 << ")" << endl; } } return 0; } ``` ## 📊 代码运行示例 输入 x = 20，输出： ``` (3, 5) (5, 7) (11, 13) (17, 19) ``` ######[AI问答 | 683点数解答 | 2026-06-05 20:06:48]