欧拉函数 ψ(x)=x*(1-1/pi) pi为x的质数因子
特殊性质（图片内容就是图片后面的文字）
欧拉函数是积性函数——若m,n互质，
ψ(m*n)=ψ(m)*ψ(n)；
当n为奇数时， 
ψ(2*n)=ψ(n);
若n为质数则 
ψ(n)=n-1;
代码实现求欧拉函数 复杂度O(n*n) （有优化会补上）
#include<bits/stdc++.h> #define int long long using namespace std; const int maxn=1000005; bool prime[maxn]; int p[maxn]; // form 1 kaishi int ou[maxn]; int cnt; // fan wei lei zhi shu ge shu void build_prime(int n) { for(int i=2;i<=n;i++) prime[i]=1; for(int i=2;i<=n;i++) { if(prime[i]==1) p[++cnt]=i; for(int j=1;j<=cnt && i*p[j]<=n;j++) { prime[i*p[j]]=0; if(i%p[j]==0) break; } } } void build_oulahanshu(int n) { for(int i=1;i<=n;i++) { int num=i; int k=1; for(int j=1;p[j]<=i && j<=cnt;j++) { if(i%p[j]==0) num*=(p[j]-1),k*=p[j]; } ou[i]=num/k; // cout<<"==="<<ou[i]<<endl; } } int32_t main() { int n; cin>>n; build_prime(n); cout<<cnt<<endl; build_oulahanshu(n); while(n--) { int x; cin>>x; cout<<ou[x]<<endl; } }
O(n log n)
#include<bits/stdc++.h> using namespace std; #define Max 1000001 int euler[Max]; int main(){ euler[1]=1; for(int i=2;i<Max;i++) euler[i]=i; for(int i=2;i<Max;i++) if(euler[i]==i) for(int j=i;j<Max;j+=i) euler[j]=euler[j]/i*(i-1); for(int i=1;i<=100;i++) { cout<<euler[i]<<" "; if( (i+1)%10==0 )cout<<endl; } }
o(n)
#include<bits/stdc++.h> using namespace std; const int maxn=1e7+10; int vis[maxn]; int prime[maxn]; int phi[maxn]; void euler(int n) { memset(vis,0,sizeof(vis)); int tot=0;
phi[1]=1; for(int i=2;i<=n;i++) { if(vis[i]==0) { vis[i]=i; prime[++tot]=i; // su shu hai phi[i]=i-1; // su shu de xian chu li } for(int j=1;j<=tot && prime[j]*i<n;j++) { if(prime[j]>vis[i] ) { // 超出ｎ的范围 或者 ｉ有比prime[j]更小的质因子； break; } // prime[j]是i*prime[j]的最小质因子 vis[i*prime[j]]=prime[j]; // phi[i*prime[j]]=phi[i]*( i%prime[j]?prime[j]-1:prime[j]); if( i%prime[j]) phi[i*prime[j]]=phi[i]*(prime[j]-1); else phi[i*prime[j]]=phi[i]*prime[j]; } } } int main() { int n=1e7+5; euler(n); cout<<phi[100000]<<endl; }