题意：

求sigma phi(n)

思路：

线性递推欧拉函数

（维护前缀和）

//By SiriusRen

#include <cstdio>

using namespace std;

#define maxn 1000005

#define int long long

int n,p[maxn+100],s[maxn+100],phi[maxn+100],tot;

void Phi(){

    for(int i=2;i<=maxn;i++){

        if(!s[i])p[++tot]=i,phi[i]=i-1;

        for(int j=1;j<=tot&&i*p[j]<=maxn;j++){

            s[i*p[j]]=1,phi[i*p[j]]=(p[j]-1)*phi[i];

            if(i%p[j]==0){

                phi[i*p[j]]=phi[i]*p[j];

                break;

            }

        }

    }

}

signed main(){

    Phi();

    for(int i=2;i<=maxn;i++)s[i]=s[i-1]+phi[i];

    for(;scanf("%lld",&n)&&n;printf("%lld\n",s[n]));

}