欧拉函数是小于等于x的整数中与x互质的数的个数,特别的φ(1)=1
欧拉函数的通式:φ(n)=n*(1-1/P1)*(1-1/P2)*(1-1/P3)*(1-1/P4)…..(1-1/Pn)
其中p1, p2……pn为x的所有质因数,x是不为0的整数
1.欧拉函数是积性函数——若m,n互质:φ(mn)=φ(m)φ(n)
2.特殊性质:当n为奇质数时:φ(2n)=φ(n)
3.若n为质数时:φ(n)=n-1
4.当n>2时,φ(n)是偶数
5.小于n的数中,与n互质的数的总和为:φ(n) * n / 2 (n>1)
6.若p为质数,n=p^k,则φ(n)=p^k-p^(k-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;
}
1.代码中的 ans-=ans/i; 这一步就是对应欧拉函数的通式
2.while(n%i==0) n/=i; 这一个语句是为了保证完全消除我们刚才得到的那个i因子。确保我们下一个得到的i是n的素因子。
3.if(n>1)ans-=ans/n; 这个语句是为了保证我们已经除完了n的所有的素因子,有可能还会出现一个我们未除的因子,如果结尾出现n>1 ,说明我们还剩一个素因子木有除。
打表
void euler(int n)
{
phi[1]=1;//1要特判
for (int i=2;i<=n;i++)
{
if (flag[i]==0)//这代表i是质数
{prime[++num]=i;
phi[i]=i-1;}
for (int j=1;j<=num&&prime[j]*i<=n;j++)//经典的欧拉筛写法
{
flag[i*prime[j]]=1;//先把这个合数标记掉
if(i%prime[j]==0)
{
phi[i*prime[j]]=phi[i]*prime[j];//若prime[j]是i的质因子,则根据计算公式,i已经包括i*prime[j]的所有质因子
break;//经典欧拉筛的核心语句,这样能保证每个数只会被自己最小的因子筛掉一次
}
else phi[i*prime[j]]=phi[i]*phi[prime[j]];//利用了欧拉函数是个积性函数的性质
}
}
}
123