POJ2478 Farey Sequence

#include<stdio.h>
#include<string.h>
#define maxn 1000001
int phi[maxn];
void p()
{
	memset(phi,0,sizeof(phi));
	for(int i=2;i<maxn;i++)
	{
		if(!phi[i])
			for(int j=i;j<maxn;j+=i)
			{
				if(!phi[j])phi[j]=j;
				phi[j]=phi[j]/i*(i-1);
			}
	}
}
int main()
{
	int n;
	p();
	while(~scanf("%d",&n)&&n)
	{
		long long ans=0;
		for(int i=2;i<=n;i++)
			ans+=(long long)phi[i];
		printf("%lld\n",ans);
	}
	return 0;
}