欧拉筛

^{（本人理解并不透彻只能简单讲一讲）}

“欧拉筛”（又称线性筛）是一种用于高效筛选素数的算法，其思想是确保每个合数仅被其最小质因子筛除一次，从而实现 O(n) 的时间复杂度。

---

最小质因子筛除

欧拉筛通过遍历每个数 i ，并用当前已筛出的质数 p_j 标记合数 i × p_j。关键在于：当 i 能被 j 整除时立即终止内层循环 if (i % p[j] == 0) break;，这保证了合数 i × p_j 仅被其最小质因子 p_j 筛除，也加快了速度。

---

积性函数的扩展性

欧拉筛不仅可用于筛素数，还可高效计算积性函数（如欧拉函数 、莫比乌斯函数 ）。在筛除合数的同时，通过最小质因子的性质递推函数值。_{（此处为网络资料）}

---

算法步骤与代码实现

const int MAX = 114514;
bool is[MAX];    // 标记是否为素数
int p[MAX], cnt; // 存储素数列表

void euler_sieve(int n) {
    memset(is, true, sizeof(is)); // 初始化全为素数
    is[0] = is[1] = false;       // 0和1非素数
    for (int i = 2; i <= n; i++) {
        if (is[i]) ps[++cnt] = i; // 记录素数
        for (int j = 1; j <= cnt && i * p[j] <= n; j++) {
            is[i * p[j]] = false; // 标记合数
            if (i % p[j] == 0) break;  // 关键：保证最小质因子筛除
        }
    }
}

整体时间复杂度是:

$$O(n)$$

---

相比于埃氏筛时间慢了许多

埃氏筛时间复杂度:O(nloglogn)

欧拉筛时间复杂度:O(n)

埃氏筛与欧拉筛空间复杂度都为: O(n)

在数据大时埃氏筛可能是更好的选则

---

适用场景

欧拉筛: 需同时计算积性函数（如φ, μ） 埃氏筛: 仅需素数表时更快（常数项小） 相比于埃氏筛，欧拉筛可以避免合数被重复标记_{（此处为网络资料）}

---

欧拉筛的核心价值

欧拉筛的核心价值在于其线性时间复杂度和最小质因子筛除的确定性，特别适合需要结合积性函数求解的题目 , 效果更加。在算法竞赛中，它十分适合处理大规模素数问题。

总之欧拉筛与埃氏筛各有好坏要按题目要求选择合适的算法 _{（本文部分由网络资料改编而成）}