思路来源：https://blog.csdn.net/qq_39763472/article/details/82428602?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522164499203516780269849497%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=164499203516780269849497&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~blog~top_positive~default-1-82428602.nonecase&utm_term=%E6%AC%A7%E6%8B%89%E7%AD%9B%E6%B3%95&spm=1018.2226.3001.4450

主要是基于线性筛素数算法，利用以下几个性质来判断即可

并且，算法保证，每个合数只被他的最小质因子筛选一次，所以就有了break

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N=1e6+5;
bool vis[N];
int euler[N];
int primes[N],cnt;
int n;

void get_euler()
{
    euler[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!vis[i])
        {
            euler[i]=i-1;
            primes[++cnt]=i;
        }
        for(int j=1;primes[j]<=n/i;j++)
        {
            int t=i*primes[j];
            vis[t]=1;
            if(i%primes[j]==0)
            {
                euler[t]=euler[i]*primes[j];
                break;
                /*已经被最小质因子筛选到，不再继续筛。
                因为primes[j+k]*i (k>0)的最小质因子是primes[j],
                需要等到i'=primes[j+k]*i/primes[j]时再筛
                */
            }
            euler[t]=euler[i]*(primes[j]-1);
        }
    }
}

int main()
{
    cin>>n;
    get_euler();
    long long ans=0;
    for(int i=1;i<=n;i++)   ans+=euler[i];
    cout<<ans<<endl;
    return 0;
}