1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 2000005 4 long long n,ans,f[N],vis[N],p[N]; 5 void mobies(int n){ 6 f[1]=1; 7 for(int i=2;i<=n;i++){ 8 if (!vis[i])f[p[++p[0]]=i]=i-1; 9 for(int j=1;j<=p[0];j++){ 10 if (p[j]*i>n)break; 11 vis[i*p[j]]=1; 12 if (i%p[j]==0)f[i*p[j]]=f[i]*p[j]; 13 else f[i*p[j]]=f[i]*(p[j]-1); 14 } 15 } 16 for(int i=2;i<=n;i++)f[i]+=f[i-1]; 17 } 18 int main(){ 19 mobies(N-5); 20 scanf("%lld",&n); 21 for(int i=1,j;i<=n;i=j+1){ 22 j=n/(n/i); 23 ans+=(f[j]-f[i-1])*(n/i)*(n/i); 24 } 25 printf("%lld",(ans-n*(n+1)/2)/2); 26 }