莫欺少年穷，修仙之旅在这开始—>算法基础课题解

可参考： 筛质数

// 1.当 i 是质数的时候，1 ～ i - 1 都与 i 互质，故 phi[i] = i - 1
// 2.当 i % primes[j] == 0 时，primes[j] 是 i 的最小质因子
//   故 i 的所有质因子都与 primes[j] * i 的质因子相同
//   而 primes[j] * i 的欧拉函数比i还多了一个 primes[j]
//   所以 phi[primes[j] * i] = phi[i] * primes[j]
// 3.当 i % primes[j] != 0 时，primes[j] 小于 i 的最小质因子
//   故 primes[j] * i 比 i 还多一个质因子 primes[j]
//   所以 primes[j] * i 的欧拉函数比 i 多了一个 primes[j](1 - 1 / primes[j]) = primes[j] - 1
//   故 phi[primes[j] * i] = phi[i] * (primes[j] - 1)

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 1000010;

int n;
int primes[N],cnt;
int phi[N];
bool st[N];

LL get_eulers(int n)
{
    phi[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!st[i])
        {
            primes[cnt++]=i;
            phi[i]=i-1; //第一种情况
        }
        for(int j=0;primes[j]<=n/i;j++)
        {
            st[primes[j]*i]=true;
            if(i%primes[j]==0)
            {
                phi[primes[j]*i]=phi[i]*primes[j]; //第二种情况
                break;
            }
            phi[primes[j]*i]=phi[i]*(primes[j]-1); //第三种情况
        }
    }

    LL res=0;
    for(int i=1;i<=n;i++) res+=phi[i];

    return res;
}

int main()
{
    cin>>n;

    cout<<get_eulers(n)<<endl;

    return 0;
}