POJ 2407 Relatives（欧拉函数）

题意：

给出一个n，求小于等于的n的数中与n互质的数有几个。

思路：

欧拉函数的作用就是用来求这个的。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<string>
 4 #include<cstring>
 5 #include<cmath>
 6 using namespace std;
 7 
 8 int n;
 9 
10 
11 int main()
12 {
13     //freopen("D:\txt.txt", "r", stdin);
14     while (cin >> n && n)
15     {
16         double ans = 1;
17         int x = n;
18         if (n == 1)
19             cout << "0" << endl;
20         else
21         {
22             for (int i = 2; i <= n; i++)
23             {
24                 if (n%i == 0)
25                 {
26                     x = x - x / i;
27                     while (n%i == 0)
28                         n /= i;
29                 }
30             }
31             if (n > 1)
32                 x = x - x / n;
33         }    
34         cout << x << endl;
35     }
36 }