欧拉函数

 

#include <iostream>
#include <cstdio>
using namespace std;
const int Max = 100000;
int euler[Max];
void Init(){   
	euler[1] = 1;  
	for(int i = 2; i < Max; i++) {
		euler[i]=i; 
	}  
	for(int i = 2; i < Max; i++) {
		if(euler[i] == i) {
			for(int j = i; j < Max; j += i) {
				euler[j]=euler[j]/i*(i-1);
			}        	
		}
	}
}
int main() {
	int n;
	Init();
	while(scanf("%d", &n) != EOF) {
		printf("%d\n", euler[n]);
	}
	return 0;
}