欧拉函数

欧拉函数

其中p1, p2……pn为x的所有质因数，x是不为0的整数。

 1 #include <iostream>
 2 #include <cmath>
 3 using namespace std;
 4 
 5 int euler(int n){
 6     int ans = n;
 7     for(int i = 2;i <= sqrt(n); i++){
 8         if(n % i == 0){
 9             ans = ans / i * (i - 1);//(1 - ( 1/i))
10             while(n % i == 0){
11                 n /= i;
12             }
13         }
14     }
15     if(n > 1){
16         ans = ans / n * (n - 1);
17     }
18     return ans;
19 }
20 
21 int main()
22 {
23     int n;
24     while(cin >> n){
25         cout << euler(n) << endl;
26     }
27     return 0;
28 }