第1关:欧拉筛法求素数
时间: 2025-06-20 21:36:24 AIGC 浏览: 32
### 欧拉筛法求素数的算法实现
欧拉筛法是一种高效的素数筛选方法，能够在 \(O(n)\) 的时间复杂度下找到指定范围内所有的素数。其核心思想是通过已知的素数逐步排除掉那些可以由较小素数乘积构成的合数。
以下是基于 C++ 实现的一个完整的欧拉筛法代码示例：
```cpp
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 1000000; // 定义最大范围
int prime[MAXN], is_prime[MAXN], cnt = 0; // prime用于存储素数，is_prime用于标记素数（0为素数，1为合数），cnt记录素数个数
void euler_sieve(int n) {
for (int i = 2; i <= n; i++) {
if (!is_prime[i]) { // 如果当前数未被标记为合数，则它是素数
prime[cnt++] = i; // 将该素数存入prime数组
}
for (int j = 0; j < cnt && i * prime[j] <= n; j++) {
is_prime[i * prime[j]] = 1; // 标记i*prime[j]为合数
if (i % prime[j] == 0) break; // 当前i能够被prime[j]整除时退出循环
}
}
}
int main() {
int n;
cout << "请输入一个正整数N：" << endl;
cin >> n;
euler_sieve(n);
cout << "N内的所有素数及个数如下：" << endl;
for (int i = 0; i < cnt; i++) {
cout << prime[i] << endl;
}
cout << "共有" << cnt << "个素数" << endl;
return 0;
}
```
#### 关键点解析
1. **初始化**
使用 `is_prime` 数组来标记某个数字是否为素数，初始状态下假设所有大于等于2的数字均为素数[^2]。
2. **外层循环**
遍历从2到n的所有数字，如果某数字未被标记为合数，则将其视为素数并保存至 `prime` 数组中[^2]。
3. **内层循环**
对于每一个新发现的素数，利用它去标记它的倍数为合数。为了避免重复标记某些数字，当满足条件 `i % prime[j] == 0` 时立即跳出循环[^2]。
4. **效率优化**
每个合数只会被其最小质因数对应的素数标记一次，因此整个过程的时间复杂度降低到了线性级别 $ O(n) $。
---
###
阅读全文
相关推荐
