Ｃ++的代码

以下是C++语言的代码实现：

int euler_phi(int n) {
    /*
    计算小于等于n且与n互质的正整数的个数
    */
    int phi = n;  // 初始化phi为n
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) {
            phi -= phi / i;
            while (n % i == 0) {
                n /= i;
            }
        }
    }
    if (n > 1) {
        phi -= phi / n;
    }
    return phi;
}

同样使用欧拉筛法，将n进行质因数分解，然后根据欧拉函数的公式计算出φ(n)的值。时间复杂度为O(sqrt(n))。