cpp欧拉筛
时间: 2025-03-25 12:06:47 浏览: 69
### C++ 中实现欧拉筛法
欧拉筛法(Euler's Sieve)是一种高效的素数筛选方法,能够在 \( O(n) \) 的时间内完成对范围内所有素数的筛选[^4]。该算法通过避免重复筛选的方式提升了性能。
以下是基于 C++ 编写的欧拉筛法的具体实现:
#### 代码示例
```cpp
#include <iostream>
#include <vector>
using namespace std;
void eulerSieve(int n) {
vector<bool> isPrime(n + 1, true); // 初始化布尔数组,默认全部为质数
vector<int> primes; // 存储找到的质数
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) break; // 关键优化:当 i 是 primes[j] 的倍数时停止
}
}
cout << "Primes up to " << n << ": ";
for (auto p : primes) {
cout << p << " ";
}
}
int main() {
int maxNumber;
cout << "Enter the maximum number: ";
cin >> maxNumber;
eulerSieve(maxNumber);
return 0;
}
```
#### 解析
上述代码实现了欧拉筛的核心逻辑:
- 使用 `isPrime` 数组记录每个数字是否为质数[^3]。
- 遍历过程中,将当前数字与已有质数的乘积累计标记为非质数。
- 当前数字如果是某个质数的整数倍时提前退出循环,这是为了防止重复筛选同一数值。
这种设计不仅减少了不必要的计算量,还保证了每个合数仅被其最小质因数筛选一次。
---
### §相关问题§
1. 如何修改此代码以统计范围内的素数数量而不存储具体素数?
2. 欧拉筛法相较于埃氏筛法的主要优势是什么?
3. 是否可以进一步优化欧拉筛的空间复杂度?如何实现?
4. 在实际应用中,哪些场景适合使用欧拉筛而非其他素数筛选方法?
5. 如果需要支持更大的数据规模,应如何调整现有代码结构?
阅读全文
相关推荐


















