题干：

在数论中，对正整数 nn，欧拉函数 \varphi (n)φ(n) 是小于等于 nn 的正整数中与 nn 互质的数的数目。

例如 \varphi (12)=4φ(12)=4，因为 1,5,7,111,5,7,11 均和 1212 互质。

代码框中的代码是一种求欧拉函数的实现，请分析并填写缺失的代码，计算出 \varphi(n)φ(n) 的值。

提示：若 n=p_{1}^}p_{2}^}\cdots p_{r}^}，则 \varphi (n)=\prod _1^{r}p_{i}^(p_{i}-1)φ(n)=∏1r​pi(​pi​−1)。

样例输入复制

无

样例输出复制

无

解题报告：

  就是个欧拉函数。

AC代码：

#include <iostream>
using namespace std;
int euler(int n) {
    int res = n;
    for (int i = 2; i <= n; i++) {
        if (n % i == 0) {
            res = res/i*(i-1);
            while (n % i == 0) {
                n /= i;
            }
        }
    }
    return res;
}
int main() {
    int n;
    cin >> n;
    cout << euler(n) << endl;
    return 0;
}

对于欧拉函数，显然我们也可以这样求解:

int E(int x)
{
   int ans = x;
   for(int i = 2; i <= sqrt(x); i++)
   {
   	    if(x % i == 0) ans=ans-ans/i;
   	    while(x%i == 0) x/=i;
   } 
   if(x != 1) ans=ans-ans/x;
   return ans;
}