欧拉函数（模板）

欧拉函数：欧拉函数是小于或等于 n 的正整数中与 n 互质的数的数目（（1）=1），

记为（n）。

欧拉函数的通式：（n）= 

欧拉函数的性质：n 的因子的欧拉函数加起来等于 n 。

1.求正整数 n 的欧拉函数：

int euler(int n){int ret=n;for(int i=2;i*i<=n;i++){if(n%i==0){ret-=ret/i;while(n%i==0) n/=i;}}if(n>1) ret-=ret/n;return ret;
}

2.欧拉函数的线性求法：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+5;
int vis[maxn],prime[maxn],phi[maxn];
signed main(){int n;cin >> n;int cnt=0;phi[1]=1;for(int i=2;i<=n;i++){if(!vis[i]) prime[++cnt]=i,phi[i]=i-1;for(int j=1;j<=cnt && i*prime[j]<=n;j++){vis[i*prime[j]]=1;if(i%prime[j]==0){phi[i*prime[j]]=phi[i]*prime[j];break;}phi[i*prime[j]]=phi[i]*(prime[j]-1);}}cout << phi[n] << endl;return 0;
}