欧拉函数（欧拉筛）--模板

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

using namespace std;

typedef long long llong;
const int MAXN = 25000000 + 10;

llong phi[MAXN + 200];
llong prime[MAXN + 200];
bool book[MAXN + 200];

void phi_prime (int n)
{
	int i, j;
	
	memset (book, true, sizeof(book));
	prime[0] = 0;
	book[0] = false, book [1] = false;
	phi[1] = 1;
	for (i = 2; i <= n; i++)
	{
		if (book[i])
		{
			prime[++prime[0]] = i;
			phi[i] = i - 1;
		}
		for (j = 1; j <= prime[0] && i * prime[j] <= n; j++)
		{
			book[i * prime[j]] = false;
			if (i % prime[j] == 0)
			{
				phi[i * prime[j]] = phi[i] * prime[j];
				break;
			}
			else
			{
				phi[i * prime[j]] = phi[i] * (prime[j] - 1);
			}
		}
	}
}

int main()
{
    int i, n, t;
    
    phi_prime(MAXN - 5);
    while(1)
    {
    	scanf("%d",&n);
    	printf("%d\n",phi[n]);
	}
    return 0;
}