https://www.luogu.com.cn/problem/P2568
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,t,ans,ph[10000005]={0,1},pr[10000005],s[10000005]={0,1};
signed main(){
cin>>n;
for(int i=2;i<=n;i++){
if(ph[i]==0) pr[++t]=i,ph[i]=i-1;
for(int j=1;j<=t&&i*pr[j]<=n;j++){
if(i%pr[j]==0) ph[i*pr[j]]=ph[i]*pr[j];
else ph[i*pr[j]]=ph[i]*(pr[j]-1);
}
}
for(int i=1;i<=n;i++) s[i]=s[i-1]+ph[i];
for(int i=1;i<=t;i++) ans+=s[n/pr[i]]*2-1;
cout<<ans;
return 0;
}