欧拉函数介绍

欧拉函数是小于x的整数中与x互质的数的个数，一般用φ(x)表示。特殊的，φ(1)=1。

求欧拉函数

void euler(int n)
{
    for (int i=1; i<=n; i++)
        phi[i]=0;
    phi[1]=1;
    for (int i=2; i<=n; i++)
    {
        if (!phi[i])//这代表i是质数
        {
            for (int j=i; j<=n; j+=i)
            {
                if(!phi[j]) phi[j]=j;
                phi[j]=phi[j]/i*(i-1);//把i的倍数更新掉
            }
        }
    }
}