给定一个正整数 $n$，求 $1∼n$ 中每个数的欧拉函数之和。

输入格式

共一行，包含一个整数 $n$。

输出格式

共一行，包含一个整数，表示 $1∼n$ 中每个数的欧拉函数之和。

数据范围

$1≤n≤10^6$

输入样例：

6

输出样例：

12

思路

1) 质数i的欧拉函数即为$phi[i] = i - 1, 1 ~ i - 1$均与$i$互质，共$i - 1$个。
2) $phi[primes[j] * i]$分为两种情况:
①$i% primes[j] == O$时:$primes[j]$是$i$的最小质因子，也是 $primes[j] * i$的最小质因子，因此$1 - 1 / primes[j]$这一项在$phi[i]$中计算过了，只需将基数$N$修正为$primes[j]$倍，最终结果为$phi[i] * primes[j]$。
②$i % primes[j] != 0$: $primes[j]$不是i的质因子，只是$primes[j] * i$的最小质因子，因此不仅需要将基数$N$修正为$primes[j]$倍，还需要乘上$\\frac{prime[j] - 1}{primes[j]} \\qquad$这一项，因此最终结果$phi[i]*(primes[j]-1)$。

AC代码

#include <iostream>

using namespace std;

const int N = 1000010;

int n;
int p[N], st[N], cnt;// 筛选质数 p[]存放已经找到的质数，st[]标记某个数是不是质数，cnt记录已经找到的质数数量
int phi[N]; // 欧拉函数 Φ(x)
long long res;

void ola_primes(int x)
{
    for (int i = 2; i <= x; i ++)
    {
        if(!st[i])
        {
            p[cnt ++] = i;
            //从1到质数i中与i互质的数个数为i-1
            phi[i] = i - 1;
        }

        for (int j = 0; p[j] <= x / i; j ++)
        {
            st[p[j] * i] = 1;

            if (i % p[j] == 0)
            {
                /*
                当p[j]是i的一个约数时,i的质因数与p[j]*i的质因数完全相同。
                i      = (p1^a1)*(p2^a2)*(p3^a3)*...(p[j]^ap[j])...(pk^ak)
                i*p[j] = (p1^a1)*(p2^a2)*(p3^a3)*...(p[j]^(ap[j]+1))...(pk^ak)
                由欧拉函数的定义可知：
                Φ(i)      =  i   * (1-1/p1)*(1-1/p2)*(1-1/p3)*...(1-1/p[j])*...(1-1/pk)
                Φ(i*p[j]) = i*p[j]*(1-1/p1)*(1-1/p2)*(1-1/p3)*...(1-1/p[j])*...(1-1/pk)
                */
                phi[i * p[j]] = p[j] * phi[i];
                break;
            }
            /*
            当i%p[j]!=0时，p[j]不是i的约数，i与i*p[j]的质因子相差一个p[j]
            i      = (p1^a1)*(p2^a2)*(p3^a3)*...(pk^ak)
            i*p[j] = (p1^a1)*(p2^a2)*(p3^a3)*...(pk^ak)*(p[j]^ap[j])
            所以由欧拉函数的定义可知：
            Φ(i)      =  i    *(1-1/p1)*(1-1/p2)*(1-1/p3)*...(1-1/pk)
            Φ(i*p[j]) = i*p[j]*(1-1/p1)*(1-1/p2)*(1-1/p3)*...(1-1/pk)(1-1/p[j])
            */
            phi[i * p[j]] = (p[j] - 1) * phi[i]; //p[j]*(p[j]-1)/p[j]*phi[i]  p[j]约了
        }
    }
}

int main()
{
    cin >> n;
    phi[1] = 1;
    ola_primes(n);
    for (int i = 1; i <= n; i ++) res += phi[i];
    cout << res;

    return 0;
}