欧拉函数定义
1∼N中与N 互质的数的个数被称为欧拉函数，记为ϕ(N)。
在算数基本定理中：
，则：
证明
设p1是 N的质因子，1∼N中p1的倍数有
,共
个。同理。若p2是N的质因子，1∼N中p2的倍数有
个。这
数中,其中既是p1的倍数，又是p2的倍数的数有N/(p1⋅p2)个。根据容斥原理，NNN中去掉p1和p2的倍数:
类似的，N的全部质因子都能使用容斥原理实现，得到与N互质的数的个数。
性质
证明性质1
若x为与n互质的数，则根据更相减损术原理，gcd(n,x)=gcd(n,n−x)=1。故，与n互质的x，n-x成对出现，总和为
性质1证毕。
证明性质2
算数基本定理中：
性质
若p是质数
证明性质3
因为p是质数，p与1∼p−1的每个数都互质，故
证明性质4
性质4证毕
证明性质5
性质5证毕
代码实现
质因数分解
代码语言：javascript复制int phi(int x){//求x的欧拉函数值
int ans=x;
for(int i=2;i*i<=x;i ){//分解x的质因数
if(x%i==0){
ans=ans/i*(i-1);
while(x%i==0){
x/=i;
}
}
}
if(x>1) ans=ans/x*(x-1);
return ans;
}线性筛
代码语言：javascript复制int erla(int n){//利用线性筛更新欧拉函数值
int cnt=0;//质数个数
v[0]=v[1]=1;//标记0和1为非质数
phi[1]=1;//记录1的欧拉函数值为1
for(int i=2;i<=n;i ){//遍历2~n
if(!v[i]){//i是质数
prime[cnt ]=i;//存储i到质数表
phi[i]=i-1;//性质3： p是质数，phi(p)=p-1
}
//遍历质数表
for(int j=0;j<cnt&&prime[j]*i<=n;j ){
v[prime[j]*i]=1;//标记质数与i的乘积为非质数
if(i%prime[j]==0){//性质4:若p%i==0,phi(i*p)=p*phi(i)
phi[i*prime[j]]=prime[j]*phi[i];
break;
}else{//性质5:若p%i!=0,phi(i*p)=(p-1)*phi(i)
phi[i*prime[j]]=(prime[j]-1)*phi[i];
}
}
}
return cnt;//返回质数个数
}Q.E.D.
