10408 - Farey sequences - UVa

题目要求：给定一个数n，求1—n之间有多少对互质的数，

phi【i】数组表示i之前有多少个和i互质的数，

a【i】表示前phi【1】+phi【2】+……+phi【i】；

a【n】数组就是1---n之间互质的数的对数。。

#include<stdio.h>
#include<string.h>

long long a[1000010],phi[1000010];
long long n,i,j;
int main()
{
	memset(a,0,sizeof(a));
	for(i=1;i<=1000000;i++)
		phi[i]=i;
	for(i=2;i<=1000000;i++){
		if(phi[i]==i)
			for(j=i;j<=1000000;j+=i)//打欧拉函数的表
				phi[j]=phi[j]/i*(i-1);
		a[i]=a[i-1]+phi[i];//求前i项和
	}

	while(scanf("%lld",&n),n){
		printf("%lld\n",a[n]);
	}
}