求解欧拉函数值

 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 }