欧拉函数： 小于或等于n的正整数中与n互质的数的数目

通式：ϕ(n)=nΠpi(1−1pi)">?(n)=nΠpi(1?1pi)?(n)=nΠpi(1?1pi) (pi">pipi为小于或等于n的正整数中与n互质的数) ， 特殊的，ϕ(1)=1">?(1)=1?(1)=1 。

由通式可得， ϕ(n)=(1−1p1)⋅(1−1p2)⋅⋯⋅(1−1pi−1)⋅(n−npi)">?(n)=(1?1p1)?(1?1p2)???(1?1pi?1)?(n?npi)?(n)=(1?1p1)?(1?1p2)???(1?1pi?1)?(n?npi)

int phi(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; // 除完所有质因子， 保证第4行正确性
        }
    if(n!=1)ans-=ans/n; // 大于sqrt(n)的最多只有一个质因子
    return ans;
}

对于倒数第三行， 小于n">n??√n的所有质因子相乘若小于n">n??√n, 那么有且只有一个大于n">n??√n的质因子， 假设有两个， 相乘必定会大于n">nn.