1953.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1953 on 2006-05-17 at 14:25:21 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int PM = 32000;

int main()
{
	bool prime[PM];
	int i, j, n, p[PM], pn = 0;
	
	memset(prime, true, sizeof(prime));
	for(i = 2; i < PM; i++) {
		if(!prime[i]) continue;
		p[pn++] = i;
		for(j = 2; i*j < PM; j++) prime[i*j] = false;
	}
	while(scanf("%d", &n) != EOF && n != 0) {
		int e = n;
		for(i = 0; i < pn && n != 1; i++) {
			if(n % p[i] == 0) e = e/p[i]*(p[i]-1);
			while(n % p[i] == 0) n /= p[i];
		}
		if(n != 1) e = e/n*(n-1);
		printf("%d\n", e);
	}
	
	return 0;
}