本文共 1430 字，大约阅读时间需要 4 分钟。
欧拉函数的定义：
若 gcd ( a , b ) = 1 \gcd(a,b)=1 gcd(a,b)=1，则 a a a和 b b b互质 在自然数1到n中与n互质的个数称为欧拉函数，记作 φ ( n ) φ(n) φ(n)易 证明：显然，质数的因数只有1和它本身，且1与任何数互质，所以除了它本身，其它都互质。
证明：与性质1类似， p k p^k pk即总数减去它的因数数量 p k − 1 p^{k-1} pk−1，由于 p k p^k pk
根据容斥定理可以得到 φ ( n ) = n ∗ ∏ ( 1 − p ) / p φ(n)=n*∏(1-p)/p φ(n)=n∗∏(1−p)/p 由于φ是积性函数，所以 φ ( a b ) = φ ( a ) ∗ φ ( b ) ( gcd ( a , b ) = 1 ) φ(ab)=φ(a)*φ(b)(\gcd(a,b)=1) φ(ab)=φ(a)∗φ(b)(gcd(a,b)=1) ∑ [ d ∣ n ] φ ( d ) = n ， ∑ [ g c d ( n , i ) = = 1 ] i = n ∗ φ ( n ) / 2 ∑[d|n]φ(d)=n，∑[gcd(n,i)==1]i=n*φ(n)/2 ∑[d∣n]φ(d)=n，∑[gcd(n,i)==1]i=n∗φ(n)/2 根据以上性质，可以用各种筛法解决#include#include #define Max 100000001using namespace std;int phi[Max],n,p[Max],pn; bool f[Max];void Phi()//φ(欧拉函数){ phi[1]=1; for(int i=2;i<=n;i++) { if(!f[i]) { p[++pn]=i; phi[i]=i-1;//根据性质，i为质数， φ(i)=i-1 } for(int j=1;j<=pn&&i*p[j]<=n;j++) { f[i*p[j]]=1; if(i%p[j]==0) { //根据通式，φ(i*p[j]) = (i*p[j])*∏(1-p)/p = (i*∏(1-p)/p)*p[j] = φ(i)*p[j] phi[i*p[j]]=phi[i]*p[j]; break; } else //否则，i和 p[j]互质，因为 p[j]是质数 phi[i*p[j]]=phi[i]*(p[j]-1);//由积性函数性质得 φ(i*p[j]) = φ(i)*φ(p[j]) = φ(i)*(p[j]-1) } }}int main(){ printf("求1~n的欧拉函数\n输入n\n"); scanf("%d",&n); Phi(); for(int i=1;i<=n;i++) { printf("1~%d中与%d互质的个数:%d\n",i,i,phi[i]); }}
转载地址：http://shpwb.baihongyu.com/