【复习笔记】无脑筛法——埃筛

欧拉筛是必须会的板子。但是，每个人最早接触的素数筛法绝对是埃筛，据说复杂度是$O(log(logn))$，好像比欧拉筛慢不了多少。洛谷的欧拉筛板子是可以过的。

作为一个蒟蒻，考场上虽然能写出欧拉筛素数，但是要筛莫比乌斯函数或者欧拉函数，够呛能魔改出来。于是我显得没事，脑糊了一下埃筛积性函数，发现竟然能筛出来。这个特别好想，基本无脑使用积性函数性质就行。

欧拉函数

void GetPhi(int n) {
    phi[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!com[i]) {
            phi[i] = i - 1;
            prm[++cnt] = i;
            for (int j = 2; j * i <= n; j++) {
                com[i * j] = 1;
                if (j % i == 0) phi[i * j] = i * phi[j];
                else phi[i * j] = phi[i] * phi[j];
            }
        }
    }
}

莫比乌斯函数

void GetMu(int n) {
    mu[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!com[i]) {
            mu[i] = -1;
            prm[++cnt] = i;
            for (int j = 2; j * i <= n; j++) {
                com[i * j] = 1;
                if (j % i == 0) mu[i * j] = 0;
                else mu[i * j] = mu[i] * mu[j];
            }
        }
    }
}

代码巨短不容易锅

版权属于：Noire02

本文链接：https://noire02.moe/archives/eratosthenes.html

北京第三区交通委提醒您：复制千万条，版权第一条。转载删出处，博主两行泪。