在數(shù)論，對(duì)正整數(shù)n，歐拉函數(shù)是小于或等于n的正整數(shù)中與n互質(zhì)的數(shù)的數(shù)目（因此φ(1)=1）。此函數(shù)以其首名研究者歐拉命名(Euler's totient function)，它又稱為Euler's totient function、φ函數(shù)、歐拉商數(shù)等。 例如φ(8)=4，因?yàn)?,3,5,7均和8互質(zhì)。 從歐拉函數(shù)引伸出來(lái)在環(huán)論方面的事實(shí)和拉格朗日定理構(gòu)成了歐拉定理的證明。

證明

設(shè)A, B, C是跟m, n, mn互質(zhì)的數(shù)的集，據(jù)中國(guó)剩余定理，A*B和C可建立一一對(duì)應(yīng)的關(guān)系。因此φ(n)的值使用算術(shù)基本定理便知， 若 則 例如 與歐拉定理、費(fèi)馬小定理的關(guān)系 對(duì)任何兩個(gè)互質(zhì)的正整數(shù)a, m(m>=2)有 即歐拉定理 當(dāng)m是質(zhì)數(shù)p時(shí)，此式則為： 即費(fèi)馬小定理。

實(shí)現(xiàn)

/*
特性 :
1.若a為質(zhì)數(shù),phi[a]=a-1;
2.若a為質(zhì)數(shù),b mod a=0,phi[a*b]=phi[b]*a
3.若a,b互質(zhì),phi[a*b]=phi[a]*phi[b](當(dāng)a為質(zhì)數(shù)時(shí),if b mod a!=0 ,phi[a*b]=phi[a]*phi[b])
*/
int m[n],phi[n],p[n],nump;
//m[i]標(biāo)記i是否為素?cái)?shù),0為素?cái)?shù),1不為素?cái)?shù);p是存放素?cái)?shù)的數(shù)組;nump是當(dāng)前素?cái)?shù)個(gè)數(shù);phi[i]為歐拉函數(shù)
int main()
{
        phi[1]=1;
    for (int i=2;i<=n;i++)
    {
        if (!m[i])//i為素?cái)?shù)
        {
            p[++nump]=i;//將i加入素?cái)?shù)數(shù)組p中
            phi[i]=i-1;//因?yàn)閕是素?cái)?shù),由特性得知    
        }    
        for (int j=1;j<=nump&&p[j]*i<=n;j++)  //用當(dāng)前已得到的素?cái)?shù)數(shù)組p篩,篩去p[j]*i
        {
            m[p[j]*i]=1;//可以確定i*p[j]不是素?cái)?shù) 
            if (i%p[j]==0) //看p[j]是否是i的約數(shù),因?yàn)樗財(cái)?shù)p[j],等于判斷i和p[j]是否互質(zhì) 
            {
                phi[p[j]*i]=phi[i]*p[j]; //特性2
                break;
            }
            else phi[p[j]*i]=phi[i]*(p[j]-1); //互質(zhì),特性3其,p[j]-1就是phi[p[j]]   
        }
    }
}