筛法求欧拉函数

​ 对于每个数 $N$ ，借助线性筛，欧拉函数可以用递推公式推出，下面分类讨论：

1. $N$ 为质数：

   此时 $N$ 与其他不是他本身的数都互质，也就是说：
   $$ \phi(N) = N - 1 $$

2. $N$ 不为质数：

   假设 $ N = p ·s$，其中 $p$ 为质数，那么又分类讨论：

   ​ a. $p \mid s$ 时，说明 $s$ 中已经含有质因子 $p$ ，所以此时：
   $$ \phi(N) = \phi(p·s) = p·\phi(s) $$

   ​ b. $p \nmid s$ 时，说明 $s$ 中不会含有质因子 $p$ ，所以此时：
   $$ \phi(N) = \phi(p·s) = p·\phi(s)·\frac{p -1}{p} = \phi(s)·(p - 1) $$

代码

void getPhi(int n){

    for (int i = 2; i <= n; i ++ ){
        if (!vis[i]){
            primes[cnt ++ ] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; primes[j] <= n / i; j ++ ){
            vis[i * primes[j]] = 1;
            if (i % primes[j] == 0){
                phi[i * primes[j]] = primes[j] * phi[i];
                break;
            }
            phi[i * primes[j]] = (primes[j] - 1) * phi[i];
        }
    }
}

完整代码(记得开long long)

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e6 + 10;

ll phi[N], primes[N], cnt;
bool vis[N];

void getPhi(int n){

    phi[1] = 1;
    for (int i = 2; i <= n; i ++ ){
        if (!vis[i]){
            primes[cnt ++ ] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; primes[j] <= n / i; j ++ ){
            vis[i * primes[j]] = 1;
            if (i % primes[j] == 0){
                phi[i * primes[j]] = primes[j] * phi[i];
                break;
            }
            phi[i * primes[j]] = (primes[j] - 1) * phi[i];
        }
    }
}

int main(){
    int n;
    cin >> n;

    getPhi(n);

    ll ans = 0;
    for (int i = 1; i <= n; i ++ )
        ans += phi[i];

    cout << ans;
    return 0;
}