51nod

题目链接：https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1136

思路：欧拉函数求小于或等于n且与n互质的数字的个数

代码：

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

View Code