欧拉函数的定义：

$1\sim N$中与$N$互质的数的个数被称为欧拉函数，记作$\phi \left ( N \right )$

 在算数基本定理中，$N= p_1^{a_1}p_2^{a_2}...p_m^{a_m}$，则：

$\phi \left ( N \right ) = N\times \frac{p_1 - 1}{p_1} \times \frac {p_2-1}{p_2}\times ...\times \frac {p_m - 1}{p_m} $

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6     int n;
 7     cin >> n;
 8     while(n--)
 9     {
10         int x,res = 0;
11         cin >> x;
12         res = x;
13         for(int i = 2;i <= x/i;++i)
14         {
15             if(x % i == 0)
16                res = res / i * (i - 1);
17             while(x % i == 0)
18                 x /= i;
19         }
20         if(x > 1)
21             res = res / x * (x - 1);//先除再乘，避免溢出
22         cout << res << endl;
23     }
24     return 0;
25 }

 

欧拉函数证明：

 

 

利用线性筛求欧拉函数：

 1 #include <iostream>
 2 using namespace std;
 3 const int N = 1000009;
 4 int prime[N],cnt,st[N];
 5 int phi[N];
 6 void euler(int n)
 7 {
 8     phi[1] = 1;
 9     for(int i = 2;i <= n;++i)
10     {
11         if(!st[i])
12         {
13             prime[cnt++] = i;
14             phi[i] = i - 1;
15         }
16         for(int j = 0;prime[j] <= n/i;++j)
17         {
18             st[prime[j] * i] = 1;
19             if(i % prime[j] == 0)
20             {
21                 phi[prime[j] * i] = prime[j] * phi[i];
22                 break;
23             }
24             phi[prime[j] * i] = phi[i] * (prime[j] - 1);
25         }
26     }
27     long long res = 0;
28     for(int i = 1;i <= n;++i)
29         res += phi[i];
30     cout << res << endl;
31 }
32 
33 int main()
34 {
35     int n;
36     cin >> n;
37     euler(n);
38     return 0;
39 }