#include<iostream>
#include<string.h>
#define maxn 1000010
using namespace std;

int phi[maxn];
long long f[maxn];
void euler()
{
    int i,j; 
    for(i=1;i<=maxn;i++) 
        phi[i]=i;
    for(i=2;i<=maxn;i+=2) 
        phi[i]/=2;
    for(i=3;i<=maxn;i+=2) 
        if(phi[i]==i) 
        {
            for(j=i;j<=maxn;j+=i)
            {
                phi[j]=phi[j]/i*(i-1);
            }
        }
}
void fun()
{
    int i;     
    euler();
    memset(f,0,sizeof(f)); 
    f[2]=1; 
    for(i=3;i<=maxn;i++) 
        f[i]=f[i-1]+phi[i];
}
int main()
{
    int n;
    fun();    
    while(cin>>n&&n)
    {         
        cout<<f[n]<<endl;                    
    }
    return 0;
}

• Re:我也是这样子。。后来人注意。。。 (815) jiqiujia 2013-07-20 16:14:35