欧拉筛cpp
时间: 2025-05-30 16:14:14 浏览: 12
### 欧拉筛法的C++实现
欧拉筛法是一种高效的线性时间复杂度算法,用于筛选一定范围内所有的素数。相比普通的埃拉托斯特尼筛法,欧拉筛法通过减少重复标记操作实现了更优的时间性能。
以下是基于引用内容整理的一个完整的欧拉筛法 C++ 实现:
```cpp
#include <iostream>
#include <vector>
using namespace std;
void EulerSieve(int n) {
vector<bool> isPrime(n + 1, true); // 初始化为true,表示可能是素数
vector<int> primes; // 存储找到的素数
isPrime[0] = isPrime[1] = false; // 0和1不是素数
for (int i = 2; i <= n; ++i) {
if (isPrime[i]) {
primes.push_back(i); // 将新发现的素数加入列表
}
for (int j = 0; j < primes.size() && i * primes[j] <= n; ++j) {
isPrime[i * primes[j]] = false; // 标记当前素数的倍数为非素数
if (i % primes[j] == 0) { // 当前i可以被primes[j]整除时退出循环
break;
}
}
}
// 打印所有素数
for (const auto& p : primes) {
cout << p << " ";
}
}
int main() {
int n;
cout << "请输入要筛选的最大数值 N:" << endl;
cin >> n;
EulerSieve(n);
return 0;
}
```
此代码的核心逻辑在于利用已知的小素数去逐步排除大数中的合数[^3]。当 `i` 能够被某个已经处理过的素数整除时,立即跳出内层循环以避免冗余计算。
#### 关键点解析
1. **初始化布尔数组**
利用一个大小为 \(n+1\) 的布尔型向量 `isPrime[]` 来记录每个数字是否可能为素数。初始状态下假设所有大于1的数都是素数[^4]。
2. **外层循环迭代**
遍历从2到\(n\)的所有整数,在每次遇到未被标记为非素数的数字时将其视为新的素数并保存下来[^3]。
3. **内层循环更新状态**
对于每一个刚确认的新素数,尝试将它的所有倍数都标记成非素数;如果某次乘积恰好能够再次分解出该素数作为因子之一,则提前终止进一步的操作以优化效率[^4]。
4. **最终输出结果**
经过一轮完整扫描之后,所有剩余仍保持原始值(true)的位置即对应着真正的素数集合。
---
###
阅读全文
相关推荐


















