推导过程:
代码:
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5;
int phi[N];
int pre[N];
void get_eulers(int n){
int tot=0;
phi[1]=1;
for(int i=2;i<=n;i++){
if(!phi[i]){
phi[i]=i-1;
pre[++tot]=i;
}
for(int j=1;j<=tot;j++){
if(pre[j]*i>n)break;
if(i%pre[j]==0){
phi[i*pre[j]]=phi[i]*pre[j];
break;
}
else phi[i*pre[j]]=phi[i]*(pre[j]-1);
}
}
}
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int n;
cin>>n;
get_eulers(n);
int ans=0;
for(int i=1;i<=n;i++){
ans+=phi[i];
}
cout<<ans;
return 0;
}