1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4 #define MMX 4000010 5 #define LL long long 6 int phi[MMX],f[MMX]; 7 LL S[MMX]; 8  9 void calc_phi(int n)        //求1--n的欧拉函数，phi[i]=φ(i)10 {11     for (int i=2;i<=n;i++)12         phi[i]=0;13     phi[1]=1;14     for (int i=2;i<=n;i++)15         if (!phi[i])16             for (int j=i;j<=n;j+=i)17             {18                 if (!phi[j])    phi[j]=j;19                 phi[j]=phi[j]/i*(i-1);20             }21 }22 23 int main()24 {25     calc_phi(MMX);26     memset(f,0,sizeof(f));27     for (int i=1;i<=MMX;i++)28         for (int j=2*i;j<=MMX;j+=i)29             f[j]+=i*phi[j/i];30 31     S[2]=f[2];32     for (int i=3;i<=MMX;i++)33         S[i]=S[i-1]+f[i];34 35     int n;36     while (cin>>n)37     {38         if (n==0) break;39         cout<<S[n]<<endl;40     }41 }