欧拉函数概念

给定一个正整数 $N$ ，欧拉函数 $\phi(N)$ 即为 $[1, N]$ 中与 $N$ 互质的数的个数。$p_i$ 为质数， $c_i$ 为次数：
$$ N = \prod p_i ^ {c_i} $$
那么：
$$ \phi(N) = N·\prod\frac{p_i - 1}{p_i} $$
代码

int phi(int n){

    int ans = n;
    for (int i = 2; i <= n / i; i ++ ){
        if (n % i == 0){
            ans = ans / i * (i - 1);
            while (n % i == 0)  
                n /= i;
        }
    }
    if (n > 1) ans = ans / n * (n - 1);

    return ans;
}