欧拉函数

/*
欧拉函数是指ｎ以内与ｎ互质的所有数的个数
通式:sum=x(1-1/p1)(1-1/p2)...(1-1/pn),其中p1, p2……pn为x的所有质因数，x是不为0的整数。
*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
typedef long long LL;
const int N=1000010;
using namespace std;
LL ans[N];
int ola(int n)
{
    int ans=1;
    for(int i=2; i*i<=n; i++) {
        if(n%i==0) {
            n/=i;
            ans*=i-1;
            while(n%i==0) {
                n/=i;
                ans*=i;
            }
        }
    }
    if(n>1)
        ans*=n-1;
    return ans;
}
/*筛选打表*/
void func()
{
    int i,j;
    for(i=2; i<N; i++) {
        if(!ans[i])
            for(j=i; j<N; j+=i) {
                if(!ans[j])
                    ans[j]=j;
                ans[j]=ans[j]/i*(i-1);
            }
    }
}
int main()
{
    int n;
    func();
    while(scanf("%d",&n),n) {
        LL sum=0;
        for(int i=2; i<=n; i++)
            sum+=ans[i];
        printf("%lld
",sum);
    }
    return 0;
}