欧拉筛法

### 欧拉筛法的算法实现与原理 #### 1. **欧拉筛法的核心思想** 欧拉筛法是一种高效的质数筛选算法，其核心在于确保每个合数仅由其最小质因数筛除一次。这种方法避免了传统埃拉托斯特尼筛法中的重复标记问题，从而显著提高了效率[^2]。 #### 2. **算法的具体步骤** 以下是欧拉筛法的主要逻辑描述： - 初始化一个布尔数组 `is_prime` 表示当前数字是否为质数，默认全部设为真。 - 使用另一个数组 `primes` 来存储已经找到的质数列表。 - 对于每一个未被标记为合数的数字 \( i \)，将其加入质数列表 `primes` 中。 - 接着，利用已知的质数列表逐一尝试将 \( i \times primes[j] \) 标记为合数，直到遇到第一个满足条件 \( i \% primes[j] == 0 \) 的情况为止。此时停止继续枚举更大的质数，因为后续产生的合数会被更小的质因子提前处理[^4]。 这种机制保证了任何合数只会以其最小质因数的形式被唯一地标记一次。 #### 3. **伪代码表示** 下面是基于上述思路构建的一个通用版本的伪代码： ```plaintext function euler_sieve(n): is_prime = array of size n+1 initialized to True primes = empty list for i from 2 to n: if is_prime[i]: add i to primes for each prime p in primes where i*p ≤ n: set is_prime[i * p] = False if i mod p == 0: break return primes ``` #### 4. **C++ 实现样例** 下面是一个完整的 C++ 程序来演示如何使用欧拉筛法找出小于等于指定数值的所有质数： ```cpp #include <iostream> using namespace std; const int MAX = 1e7 + 5; bool notPrime[MAX]; int primes[MAX], cnt; void EulerSieve(int limit){ fill(notPrime, notPrime + limit + 1, false); for(long long i=2;i<=limit;i++){ if(!notPrime[i]){ primes[cnt++] = i; } for(int j=0;j<cnt && i*primes[j]<=limit ;j++){ notPrime[i * primes[j]] = true; if(i % primes[j]==0){ break; } } } } int main(){ int N; cin >> N; EulerSieve(N); for(int i=0;i<cnt;i++) cout << primes[i] << ' '; } ``` 此程序定义了一个函数 `EulerSieve()` ，该函数接收上限参数并执行相应的筛选过程；最后输出所有发现的质数[^4]。 #### 5. **时间复杂度分析** 由于每个合数都恰好被访问一次，因此整个算法的时间复杂度接近线性级别——具体来说就是 O(n)[^2] 。这使得它非常适合大规模数据集上的运算需求。 --- ###