Source Code

Problem: 2478  User: chenxuan123456789 
Memory: 12132K  Time: 313MS 
Language: GCC  Result: Accepted 

Source Code 
#include <stdio.h>
#include <string.h>
#define N 1000001
int prime[N];
__int64 ans[N];
int main()
{
	int i,j,k;
    prime[0] = 0;
	prime[1] = 0;
	for(i=2;i<N;i++)
		prime[i] = 1;
	for(i=2;i*i<=N;i++)
	{
		if(prime[i])
		{
			for(j=i*i;j<=N;j+=i)
				prime[j] = 0;
		}
	}
	for(i=1;i<=N;i++)
	{
		ans[i] = i;
	}
	for(i=2;i<=N;i++)
	{
		if(prime[i])
		{
			for(j=i;j<N;j+=i)
				ans[j]=(ans[j]/i)*(i-1);
		}
	}
	for(i=3;i<=N;i++)
	ans[i] += ans[i-1];
	while(scanf("%d",&k)!=EOF&&k)
	{
		printf("%I64d\n",ans[k]);
	}
	return 1;
}

• Re:附代码！ (64) 508618087 2013-03-11 20:56:32