欧拉函数_1

欧拉函数_1

科技前沿 • 2025-03-08 23:49 • 阅读 47

大家好，我是讯享网，很高兴认识大家。

欧拉函数

一.什么是欧拉函数

欧拉函数就是指：对于一个正整数n，小于或等于n的正整数中与n互质的正整数个数（包括1）的个数，记作 φ ( n )

所以其通式为： φ ( n ) = n * (1 - 1/p1) * (1 - 1/p2) * …… * (1 - 1/pn),其中p1,p2……pn为n的所有质因数，例如：φ ( 10 ) 的质因数为2，5，所有φ ( 10 ) = 10 * (1 - 1/2) * (1 - 1/5) = 4(1,3,7,9这四个数)
同时φ ( 1 ) = 1；

二.欧拉函数的一些性质

若n为质数，则φ ( n ) = n - 1;
若m与n互质，则φ ( n*m ) = φ ( n ) * φ ( m );
若正整数n与a互质，那么就有
若n为奇数时，φ ( 2n ) = φ ( n );
若n = p^k且p是质数，那么φ ( n ) = (p - 1) * p^k-1 = p^k - p^k-1.

三.模板代码

1.求单个欧拉函数的模板代码

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

讯享网

2.求1~n的欧拉函数模板代码

讯享网void euler() { E[1]=1; for(int i=2;i<maxn;i++) E[i]=i; for(int i=2;i<maxn;i++){ if(E[i]==i) for(int j=i;j<maxn;j+=i){ E[j]=E[j]/i*(i-1); } } /*求前缀欧拉函数就需要这样for累加 for(int i = 2; i <= maxn; i++) E[i] += E[i-1]; */ }

3.欧拉筛与欧拉函数模板代码

bool b[maxn];//第 i 个数为合数时 b[i] = true int prime[maxn],cnt,p[maxn];//prime[i] : 第 i 个质数为prime[i];p[ i ] : 欧拉函数 void euler(int n) { p[1]=1; for(int i=2;i<=n;++i) { if(!b[i]) { prime[++cnt]=i; p[i]=i-1; } for(int j=1;j<=cnt&&prime[j]*i<=n;j++ { b[i*prime[j]] = true; if (i%prime[j]==0) { p[i*prime[j]]=p[i]*prime[j]; break; } else { p[i*prime[j]]=p[i]*p[prime[j]]; } } } }