1 /*************************************************************************
2 > File Name: phi.cpp
3 > Author: wangzhili
4 > Mail: wangstdio.h@gmail.com
5 > Created Time: 2014年03月17日 星期一 21时05分09秒
6 ************************************************************************/
7 #include<iostream> //求解欧拉函数值(小于等于n的数中与n互质的数的个数);
8 using namespace std;
9 const int MAX = 1111111;
10 int minDiv[MAX], phi[MAX], sum[MAX];
11 void getphi(){
12 for(int i = 1;i <= MAX;i ++){
13 minDiv[i] = i;
14 }
15 for(int i = 2;i * i < MAX;i ++){ //求解j的最小质因数;
16 if(i == minDiv[i]){
17 for(int j = i * i;j < MAX;j += i){
18 minDiv[j] = i;
19 }
20 }
21 }
22 phi[1] = 1;
23 for(int i = 2;i < MAX;i ++){
24 phi[i] = phi[i / minDiv[i]];
25 if((i / minDiv[i]) % minDiv[i] == 0){
26 phi[i] *= minDiv[i];
27 }else{
28 phi[i] *= (minDiv[i] - 1);
29 }
30 }
31 }
32
33 int main(){
34 int n;
35 getphi();
36 while(cin >> n){
37 cout << phi[n] << endl;
38 }
39 return 0;
40 }