线性筛法筛素数、莫比乌斯函数、欧拉函数

线性筛法（欧拉筛法）可以在 的时间内获得 的所有素数。算法保证每个合数都会被它的最小质因子筛掉，所以复杂度是线性的。同时，我们可以利用这一特性，结合积性函数的性质，在 的时间内筛出一些积性函数的值。

欧拉函数

欧拉函数 的定义为：小于 的正整数中与 互质的数的个数，。

当 为质数时，根据定义，显然有 。

设 ，其中 为素数，则有

设 为 最小质因子，，在线性筛中， 通过 被筛掉。

当 ，即 时， 含有 的所有质因子，则有

当 ，即 时， 与 互质，根据积性函数的性质有

莫比乌斯函数

莫比乌斯函数 的定义：

设 ，其中 为素数

当 为质数时，根据定义，显然有 。

设 为 最小质因子，，在线性筛中， 通过 被筛掉。

当 ，即 时，由定义得

当 ，即 时， 有 个质因子，此时我们分情况讨论，若 ，即 的所有质因子次数均为 ，根据定义有

若 ，说明 ，根据定义显然有

此时 仍然成立。

模板

bool isNotPrime[MAXN + 1];
int mu[MAXN + 1], phi[MAXN + 1], primes[MAXN + 1], cnt;
inline void euler()
{
    isNotPrime[0] = isNotPrime[1] = true;
    mu[1] = 1;
    phi[1] = 1;
    for (int i = 2; i <= MAXN; i++)
    {
        if (!isNotPrime[i])
        {
            primes[++cnt] = i;
            mu[i] = -1;
            phi[i] = i - 1;
        }

        for (int j = 1; j <= cnt; j++)
        {
            int t = i * primes[j];
            if (t > MAXN) break;

            isNotPrime[t] = true;

            if (i % primes[j] == 0)
            {
                mu[t] = 0;
                phi[t] = phi[i] * primes[j];
                break;
            }
            else
            {
                mu[t] = -mu[i];
                phi[t] = phi[i] * (primes[j] - 1);
            }
        }
    }
}