欧拉函数

这是欧拉函数，但是我看不懂

这是欧拉

老师给的正解在下面：

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 long long n,ans;
 5 int main()
 6 {
 7     freopen("phi.in","r",stdin);
 8     freopen("phi.out","w",stdout);
 9     scanf("%lld",&n);
10     ans=n;
11     int i=1;
12     while(n!=1)
13     {
14         i++;
15         if(n%i==0)
16         {
17             ans=ans/i*(i-1);
18             n=n/i;
19         }
20         while(n%i==0) n=n/i;
21     }
22     printf("%lld",ans);
23     return 0;
24 }    //看不懂，但大概是个高逼格的算法

试着用流程图画了一下

画完还是不懂

那就硬记吧（

这里给大家安利一下我的暴力算法

如果爆零的话抱歉了（

 1 #include<cstdio>
 2 using namespace std;
 3 bool huzhi(int m,int n)    //判断是否互质 
 4 {
 5     if(n % m == 0)    return false;    //能整除的肯定不互质 
 6     if(n % m == 1)    return true;    //余1的肯定互质了 
 7     return huzhi(n % m,m);    //参考某gcd算法 
 8 }
 9 int main()
10 {
11     freopen("phi.in","r",stdin);
12     freopen("phi.out","w",stdout);
13     int n,tot = 1;
14     scanf("%d",&n);
15     for(int i = 2;i <= n;i++){
16         if(huzhi(i,n))    tot++;    //简单易懂 
17     }
18     printf("%d",tot);
19     return 0;
20 }    //我也不知道这代码可以得几分

没了