C++素数

### C++ 中素数的实现方法 #### 使用暴力算法检测单个数字是否为素数 对于给定的一个正整数 \( n \)，可以通过遍历从 2 到 \( \sqrt{n} \) 的所有整数来检查是否存在能整除 \( n \) 的数。如果不存在这样的数，则说明该数是素数。 ```cpp #include <iostream> #include <cmath> bool isPrime(int num) { if (num <= 1) return false; for (int i = 2; i <= sqrt(num); ++i) { if (num % i == 0) return false; } return true; } int main() { int number; std::cout << "Enter a positive integer: "; std::cin >> number; if (isPrime(number)) { std::cout << number << " 是素数。\n"; } else { std::cout << number << " 不是素数。\n"; } return 0; } ``` 这种方法的时间复杂度大约为 O(\( \sqrt{n} \))[^1]。 #### 埃拉托斯特尼筛法获取指定范围内全部素数 当目标是从某个区间内找到所有的素数时，埃氏筛是一种高效的解决方案。此算法通过标记合数的方式逐步排除非素数候选者，最终留下的是素数列表。 ```cpp #include <vector> #include <iostream> std::vector<int> sieveOfEratosthenes(int limit) { std::vector<bool> prime(limit + 1, true); std::vector<int> primes; for (int p = 2; p * p <= limit; ++p) { if (prime[p]) { for (int multiple = p * p; multiple <= limit; multiple += p) { prime[multiple] = false; } } } for (int p = 2; p <= limit; ++p) { if (prime[p]) primes.push_back(p); } return primes; } int main() { int upperBound; std::cout << "输入上限值："; std::cin >> upperBound; auto result = sieveOfEratosthenes(upperBound); std::cout << "以下是小于等于 " << upperBound << " 的所有素数：" << '\n'; for (const auto& elem : result) std::cout << elem << ' '; return 0; } ``` 上述代码实现了经典的埃拉托斯特尼筛法，其时间复杂度接近线性级别O(n log(log n)), 对于较大的数值范围来说性能优越得多[^3]。 #### 改进版——欧拉筛（线性筛） 相比于传统的埃拉托斯特尼筛法，欧拉筛能够进一步减少重复操作次数，从而提高效率至真正的线性时间复杂度O(n). ```cpp #include <vector> #include <iostream> void eulerSieve(int maxNum) { std::vector<int> primes; bool* notPrime = new bool[maxNum + 1]; memset(notPrime, 0, sizeof(bool)*(maxNum + 1)); for (long long i = 2; i <= maxNum; ++i){ if (!notPrime[i]){ primes.push_back(i); } for (size_t j = 0; j < primes.size(); ++j){ if (primes[j]*i > maxNum) break; notPrime[primes[j]*i]=true; if (!(i%primes[j])) break; } } delete[] notPrime; // 输出结果... for(auto &elem : primes){ printf("%d ", elem); } } int main(){ int N=1e7; eulerSieve(N); return 0; } ``` 这段程序展示了如何使用更先进的技术优化素数查找过程，适用于处理更大规模的数据集.