用埃式筛法求质数c++

### C++ 实现埃氏筛法求素数 以下是基于埃氏筛法原理编写的 C++ 示例代码，能够高效地找到指定范围内所有素数： ```cpp #include <iostream> #include <vector> using namespace std; // 定义函数 sieveOfEratosthenes 来实现埃氏筛法 vector<int> sieveOfEratosthenes(int n) { vector<bool> prime(n + 1, true); // 初始化布尔数组，默认全部为素数 prime[0] = prime[1] = false; // 0 和 1 非素数 for (int p = 2; p * p <= n; p++) { // 只需遍历至 sqrt(n) if (prime[p]) { // 如果当前数是素数 for (int i = p * p; i <= n; i += p) { // 将其倍数标记为非素数 prime[i] = false; } } } vector<int> primes; // 存储最终的素数列表 for (int p = 2; p <= n; p++) { if (prime[p]) primes.push_back(p); } return primes; } int main() { int n; cout << "Enter the upper limit to list all prime numbers: "; cin >> n; vector<int> primes = sieveOfEratosthenes(n); cout << "Prime numbers up to " << n << ": "; for (int prime : primes) { cout << prime << " "; } cout << endl; return 0; } ``` 上述代码实现了埃氏筛法的核心逻辑[^1]。通过创建一个布尔数组 `prime` 表示每个数的状态（是否为素数），并逐步将已知素数的倍数标记为非素数。 #### 关键点解析 - **初始化布尔数组**：初始假设所有大于等于 2 的数都是素数。 - **优化循环条件**：只需检查到 \( \sqrt{n} \)，因为更大的因数必然有对应的小于 \( \sqrt{n} \) 的配对因子。 - **减少冗余计算**：从 \(p^2\) 开始标记倍数，而非从 \(2p\) 开始，进一步提升效率[^4]。 --- ### 问题

### 关于优化埃氏筛法求素数的C++实现 #### 使用布尔数组减少空间占用 为了提高效率，可以采用布尔类型的数组来标记哪些数字是素数。相比于整型或其他更大类型的数据结构，布尔数组能够显著降低内存消耗。 ```cpp #include <vector> using namespace std; vector<int> optimizedSieve(int n) { vector<bool> isPrime(n + 1, true); vector<int> primes; for (int p = 2; p * p <= n; ++p) { if (isPrime[p]) { for (int i = p * p; i <= n; i += p) isPrime[i] = false; } } for (int p = 2; p <= n; ++p) { if (isPrime[p]) primes.push_back(p); } return primes; } ``` 此方法通过仅遍历奇数以及从 \(p^2\) 开始筛选倍数的方式减少了不必要的运算次数[^1]。 #### 并行化处理提升性能 对于大规模数据集而言，并行执行能有效缩短运行时间。利用多线程技术可以在支持并发操作的硬件平台上进一步加速计算过程。 ```cpp #include <thread> #include <mutex> void parallelMarkNonPrimes(vector<bool>& isPrime, int start, int end, mutex& m) { for (int p = start; p*p <= end; ++p) { if (!isPrime[p]) continue; lock_guard<mutex> guard(m); // Ensure thread safety when accessing shared resource for (int multiple = max(start, p*p); multiple <= end; multiple+=p){ isPrime[multiple]=false; } } } // Split work among threads based on available hardware concurrency level. const unsigned numThreads = thread::hardware_concurrency(); vector<thread> workers(numThreads); for(unsigned t=0;t<numThreads;++t){ const auto begin=(minValue+t*chunkSize)+((t==numThreads-1)?(n-(minValue+numThreads*chunkSize)):0); workers[t]=thread(parallelMarkNonPrimes,isPrime,begin,end,std::ref(m)); } for(auto &work :workers ) work.join(); ``` 上述代码展示了如何分割任务给多个线程并让它们各自负责一部分范围内的非质数标记工作[^2]。 #### 减少冗余检查以加快速度 另一个重要的优化手段是在主循环中跳过偶数（除了2），因为所有大于2的偶数都不是质数。这不仅简化了逻辑也提高了程序的整体表现。 ```cpp if (number >= 2) { primes.push_back(2); } for (long long candidate = 3; candidate <= number; candidate += 2) { bool still_prime = true; for (auto factor : primes) { if ((candidate % factor == 0)) { still_prime = false; break; } if (factor * factor > candidate) break; } if (still_prime) primes.push_back(candidate); } ``` 这种方法避免了大量的除法运算，从而提升了算法的速度和效率[^3].