埃氏筛法优化求素数 c++

### 关于优化埃氏筛法求素数的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].