在数论,对正整数n,欧拉函数是小于n的正整数中与n互质的数的数目(φ(1)=1)。此函数以其首名研究者欧拉命名(Euler’s totient function),它又称为Euler’s totient function、φ函数、欧拉商数等。

直接求

int phi(int x){
    int res=x,a=x;
    for(int i=2;i*i<=x;i++){
        if(a%i==0){
            res=res/i*(i-1);
            while(a%i==0)a/=i;
        }

    }
    if(a>1)res=res/a*(a-1);
    return res;
}

打表

int phi[MAXN];
int get_Euler(){
    phi[1]=1;
    for(int i=2;i<=MAXN;i++)
        phi[i]=i;
    for(int i=2;i<MAXN;i++){
        if(phi[i]==i)
            for(int j=i;j<MAXN;j+=i)
                phi[j]=phi[j]/i*(i-1),cout<<j<<" "<<phi[j]<<endl;
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注