线性塞求1到一亿的质数c++
时间: 2024-10-07 07:04:04 浏览: 12
在C++中,我们可以使用线程和筛法(如埃拉托斯特尼筛法)来找出1到一亿之间的所有质数。这里是一个简单的示例,利用线程并行处理每个区间来提高效率:
```cpp
#include <iostream>
#include <vector>
#include <thread>
#include <mutex>
std::mutex mtx; // 互斥锁用于同步数据
// 核心函数,检查单个范围内的素数
void checkPrimes(int start, int end) {
for (int i = start; i <= end; ++i) {
bool isPrime = true;
for (int j = 2; j * j <= i; ++j) {
if (i % j == 0) {
isPrime = false;
break;
}
}
std::lock_guard<std::mutex> lock(mtx);
if (isPrime && i > 1)
std::cout << i << " ";
}
}
int main() {
const int n = 1e8;
const int threads_count = std::thread::hardware_concurrency(); // 获取可用核心数
std::vector<std::thread> threads;
int step = n / threads_count;
// 创建并启动线程
for (int i = 0; i < threads_count; ++i) {
int start = i * step + 1;
int end = (i == threads_count - 1) ? n : start + step - 1;
threads.emplace_back(checkPrimes, start, end);
}
// 等待所有线程完成
for (auto& t : threads) {
t.join();
}
return 0;
}
```
这个程序首先计算出每个线程需要处理的范围,然后创建并启动对应的线程。每个线程内部执行埃拉托斯特尼筛选算法,找到指定范围内的质数,并通过互斥锁确保打印结果的线程安全。
注意,对于非常大的数范围,这可能会消耗较多内存,因为每个线程都会保存整个范围的副本。此外,实际生产环境中可能还需要优化线程管理和资源分配。