cpp求质数

以下是几种常见的 C++ 实现求质数的方法及其代码示例： ### 方法一：暴力枚举法 通过逐一检查每个数字是否可以被小于其平方根的任何正整数整除来判断它是否为质数。 ```cpp #include <iostream> using namespace std; bool isPrime(int n) { if (n <= 1) return false; for (int i = 2; i * i <= n; ++i) { // 只需检查到 sqrt(n) if (n % i == 0) return false; } return true; } int main() { int start = 100, end = 200; for (int num = start; num <= end; ++num) { if (isPrime(num)) { cout << num << " 是素数" << endl; } } return 0; } ``` 这种方法的时间复杂度较高，适用于较小范围内的质数查找[^1]。 --- ### 方法二：埃拉托斯特尼筛法（Sieve of Eratosthenes） 该方法利用一个布尔数组标记哪些数字是质数，并逐步排除掉所有非质数。 ```cpp #include <iostream> #include <vector> using namespace std; void sieveOfEratosthenes(int maxNum) { vector<bool> isPrime(maxNum + 1, true); isPrime[0] = isPrime[1] = false; // 0 和 1 不是质数 for (int p = 2; p * p <= maxNum; ++p) { if (isPrime[p]) { for (int multiple = p * p; multiple <= maxNum; multiple += p) { isPrime[multiple] = false; } } } // 输出所有的质数 for (int i = 2; i <= maxNum; ++i) { if (isPrime[i]) { cout << i << " "; } } } int main() { int range = 200; sieveOfEratosthenes(range); return 0; } ``` 此算法效率更高，在较大范围内寻找质数时表现更优[^4]。 --- ### 方法三：线性筛法（欧拉筛法） 相比传统的埃氏筛法，线性筛法能够进一步优化时间复杂度至 O(n)，适合更大规模的数据处理。 ```cpp #include <iostream> #include <vector> using namespace std; void linearSieve(int maxNum) { vector<int> primes; vector<bool> isNotPrime(maxNum + 1, false); for (int i = 2; i <= maxNum; ++i) { if (!isNotPrime[i]) { primes.push_back(i); // 如果未被标记，则是一个新的质数 } for (size_t j = 0; j < primes.size() && i * primes[j] <= maxNum; ++j) { isNotPrime[i * primes[j]] = true; // 将当前数与已知质数的乘积标记为非质数 if (i % primes[j] == 0) break; // 关键剪枝条件 } } // 输出所有质数 for (auto prime : primes) { cout << prime << " "; } } int main() { int range = 200; linearSieve(range); return 0; } ``` 这种筛选方式不仅高效而且易于扩展，特别适合作为构建大规模质数表的基础工具[^4]。 --- ### 方法四：回文素数检测 除了单纯找出某个区间中的全部素数外，还可以结合特定需求完成更加复杂的任务，比如统计给定上限下的所有回文素数数量。 ```cpp #include <iostream> using namespace std; bool isPalindrome(int num) { int original = num, reversed = 0; while (num > 0) { reversed = reversed * 10 + num % 10; num /= 10; } return original == reversed; } bool isPrime(int n) { if (n <= 1) return false; for (int i = 2; i * i <= n; ++i) { if (n % i == 0) return false; } return true; } int countPalindromicPrimes(int limit) { int count = 0; for (int i = 2; i <= limit; ++i) { if (isPrime(i) && isPalindrome(i)) { count++; } } return count; } int main() { int upperLimit = 1000; cout << "在 " << upperLimit << " 以内共有 " << countPalindromicPrimes(upperLimit) << " 个回文素数。" << endl; return 0; } ``` 这段代码展示了如何综合运用多个函数逻辑解决实际问题的能力[^3]。 --- ####