欧拉函数

欧拉函数是小于等于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