pku 2478 Farey Sequence 歐拉函數
#include <iostream>
using namespace std;
const int size=1000005;
bool ok[size];
int ph[size];
int prime[size];
__int64 sum[size];
int pn;
int n;
void getph()

{
int i,j;
pn=0;
for(i=2;i<size;i++)
{
if(!ok[i])
{
prime[pn++]=i;
ph[i]=i-1;
}
for(j=0;(j<pn)&&(i*prime[j]<size);j++)
{
ok[i*prime[j]]=1;
if((i%prime[j])==0)
{
ph[i*prime[j]]=ph[i]*prime[j];
break;
}
else
ph[i*prime[j]]=ph[i]*(prime[j]-1);
}
}
}
int main()

{
ph[1]=1;
getph();
for(int i=2;i<size;i++)
sum[i]=sum[i-1]+ph[i];
while(scanf("%d",&n)!=EOF&&(n!=0))
printf("%I64d\n",sum[n]);
return 0;
}

