pku2478.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 41 行

#include <stdio.h>
#define SIZE 1000001

__int64 ans[SIZE];

void pre()
{
	int i, j, k;
	for (i = 0; i < SIZE; i++)
	{
		ans[i] = i;
	}
	for (i = 2; i < SIZE; i++)
	{
		if (ans[i] != i)
		{
			continue;
		}
		for (j = 1; i * j < SIZE; j++)
		{
			ans[i * j] = ans[i * j] - ans[i * j] / i;
		}
	}
	for (i = 3; i < SIZE; i++)
	{
		ans[i] += ans[i - 1];
	}
}

int main()
{
	int N;
	pre();
	while (scanf("%d", &N) != -1 && N)
	{
		printf("%I64d\n", ans[N]);
	}
	return 0;
}