欧拉函数

ybe2007 · 2022-05-04 13:58:41 · 个人记录

欧拉函数，符号为 φ(n) 。对于一个正整数 n ， φ(n)的值是小于等于 n 的正整数中与 n 互质的数的个数。（如 φ(6)=2 ，两数为 1,5）

欧拉函数的三个性质

• φ(1)=1

• 对于 φ(p)，若 p∈P ，则有 φ(p)=p-1 （素数集简单记为 P）

• 欧拉函数是积性函数。即如果 gcd(a,b)=1 ，那么φ(a) * φ(b)=φ(a*b)

有了这三个性质，我们就可以用线性筛处理出欧拉函数值了。

贴代码

void Euler()
{
    phi[1]=1;
    for(int i=1;i<N;i++)
    {
        if(!isp[i]) phi[i]=i-1,p[++cnt]=i;//质数的欧拉函数值是自身数值-1 
        for(int j=1;j<=cnt;j++)
        {
            if(i*p[j]>=N) break;
            isp[i*p[j]]=1;//标记合数 
            if(i%p[j]==0)
            {
                phi[i*p[j]]=phi[i]*p[j];
                break;
                //线性筛中，每一个合数都是被最小的质因子筛掉，以保证 O(n)的时间复杂度，同时计算出其phi值
                //i%p[j]==0说明i中包含了i*p[j]的所有质因子（具体原因？。。），所以φ(i*p[j])=p[j]*φ(i) 
            }
            phi[i*p[j]]=phi[i]*phi[p[j]];
            //p[j]为质数，i不是p[j]的倍数，所以gcd(p[j],i)=1，则满足积性函数性质 
        }
    }
}

效率较高，为 O(n) 。

还有一种求欧拉函数的方法是用埃氏筛求，时间复杂度 O(nlogn) 。它的主要依据是：

其中p是x的质因子。