C++欧拉筛

<think>嗯，用户想了解如何在C++中实现欧拉筛法以及它的原理。首先，我需要回忆一下欧拉筛法的基本概念。欧拉筛法，也叫线性筛，是一种高效的素数筛选算法，时间复杂度是O(n)，比埃拉托斯特尼筛法更优，因为它避免了重复标记合数的问题。 首先，用户提到了参考内容中的代码模板。我需要解释这段代码的结构和关键点。比如，代码中的vis数组是用来标记是否为合数，prime数组存储素数，cnt是素数的计数器。循环从2开始，对于每个i，如果未被标记（vis[i]为假），则i是素数，加入prime数组。然后内层循环用当前i和已找到的素数prime[j]相乘，标记其乘积为合数，并且当i能被prime[j]整除时跳出循环，避免重复标记。 这里需要注意为什么要在i能被prime[j]整除时停止。因为这样可以确保每个合数只被其最小的质因数筛掉。例如，当i是4，prime[j]是2时，4*2=8，但之后如果继续用更大的质数（比如3），4*3=12，但实际上12的最小质因数是2，应该在i=6的时候被筛掉。所以及时跳出循环保证了每个合数只被筛一次，这就是线性时间复杂度的关键。 接下来，用户可能需要了解欧拉筛法的原理，尤其是如何确保线性时间复杂度。要详细说明每个合数如何被其最小质因数筛掉，以及算法如何避免重复标记。同时，对比埃拉托斯特尼筛法，指出欧拉筛法的优势在哪里。 在实现方面，用户可能需要代码的逐行解释，比如变量的作用，循环的条件，以及关键步骤的意义。比如vis数组初始化为全0，当被标记为1时表示是合数。prime数组动态增长，保存找到的所有素数。 另外，用户可能关心时间复杂度的证明，虽然引用中提到了O(n)，但需要简要说明为什么是线性的。每个合数只被标记一次，而外层循环遍历每个数，内层循环的次数对于每个i来说有限，因此总体是线性的。 可能用户还会遇到一些常见问题，比如数组大小的设置，如何处理大范围的n，或者如何优化空间。根据引用[2]，虽然空间复杂度是O(n)，但可以微调，比如动态分配内存或者使用位运算来压缩空间，但需要权衡时间效率。 最后，生成相关问题时要围绕欧拉筛法的扩展，比如与其他筛法比较、时间复杂度的分析、错误排查以及大数处理等。这些问题能帮助用户更深入理解算法。</think>### C++欧拉筛法实现与原理分步解析 #### 一、算法原理 欧拉筛法（线性筛）的核心思想是**确保每个合数仅被其最小质因数筛除**。相比时间复杂度$O(n \log \log n)$的埃拉托斯特尼筛法，欧拉筛法通过避免重复标记实现$O(n)$时间复杂度[^2]。 关键原理： 1. 每个合数$N$都有唯一的最小质因数$p_{min}$ 2. 当遍历到$i = N/p_{min}$时，通过$i \times p_{min}$标记$N$ 3. 遇到$i \% prime[j] == 0$时终止内循环，防止大质因数重复标记 #### 二、代码实现模板 ```cpp #include <iostream> #include <cstring> using namespace std; const int MAXN = 1e6; // 筛数范围 bool vis[MAXN+5]; // 标记数组（true=合数） int prime[MAXN+5]; // 素数存储数组 int cnt = 0; // 素数计数器 void sieve(int n) { memset(vis, 0, sizeof(vis)); for(int i=2; i<=n; ++i) { if(!vis[i]) prime[++cnt] = i; // 发现素数 for(int j=1; j<=cnt && i*prime[j]<=n; ++j) { vis[i*prime[j]] = 1; // 标记合数 if(i % prime[j] == 0) break;// 关键终止条件 } } } ``` #### 三、关键代码解读 1. **外层循环**：`for(int i=2; i<=n; ++i)` - 遍历2到n的所有整数，i既可能作为基数，也可能作为倍数 2. **素数识别**：`if(!vis[i]) prime[++cnt] = i` - 未被标记的i一定是素数 3. **内层筛除**：`for(int j=1; j<=cnt && i*prime[j]<=n; ++j)` - 用当前i与所有已知素数相乘生成合数 - 边界条件`i*prime[j]<=n`防止数组越界 4. **终止条件**：`if(i % prime[j] == 0) break` - 保证合数$i \times prime[j]$仅被其最小质因数标记 - 例如：当i=4遇到prime[j]=2时（4%2==0），若不跳出，后续prime[j]=3时将标记12=4×3，但12的最小质因数是2，应在i=6时通过6×2=12标记 #### 四、时间复杂度证明 1. **每个合数仅被标记一次** - 设合数$N = p_{min} \times M$，当且仅当i=M且prime[j]=p_min时被标记 2. **总操作次数=素数个数+合数个数=n-1** - 时间复杂度严格为$O(n)$[^2] #### 五、应用场景对比 | 筛法类型 | 时间复杂度 | 空间复杂度 | 适用场景 | |----------|------------|------------|-------------------| | 埃氏筛 | O(nloglogn)| O(n) | 快速获取近似结果 | | 欧拉筛 | O(n) | O(n) | 精确获取所有素数 | | 分段筛 | O(n) | O(√n) | 超大范围筛数 |