#include <cstdio>
int n;
const int MAX = 1000001;
int sushu[200];
bool comp[1000];
__int64 phy[MAX];
__int64 tab[MAX];
__int64 ans;
int c = 0;

int main()
{
    phy[1] = 1;
	tab[1] = 0;
	sushu[0] = 2;
	int i, j;    
	for(i = 2; i < 1000; i++)
	{
		if(!comp[i])
		{
			for(j = i * 2; j < 1000; j += i)
			{
				comp[j] = 1;
			}
		}
	}
	for(i = 2; i < 1000; i++)
	{
		if(!comp[i])
		{
			sushu[c ++] = i;
		}
	} 
	for(j = 2; j < MAX; j ++)
	{
		for(i = 0; i < c ;i ++)
		{
			int k = j/sushu[i];
			if(j%sushu[i] == 0)
			{
				if(k%sushu[i] == 0)
					phy[j] = phy[k]*sushu[i];
				else
					phy[j] = phy[k]*(sushu[i] - 1);
				break;
			}
		}
		if(i == c)
			phy[j] = j - 1;
	}

	for(i = 2; i < MAX; i ++)
		tab[i] = tab[i - 1] + phy[i];
	while(scanf("%d", &n) && n)
	{		
		printf("%I64d\n", tab[n]);	
	}	
	return 0;
}

• Re:600多ms 还能怎么优化？？ (295) wqb0039 2006-09-29 09:25:34
  • 同问! (333) 875600 2007-06-22 17:59:40
• 将int k = j/sushu[i]移到括号内时间就缩半了... (948) mayp 2007-03-27 15:38:45