$\Huge\color{orchid}{点击此处获取更多干货}$

欧拉函数

实现方面其实照着定义，分解质因数然后代入公式就可以了，这里主要解释一下这个公式可以怎么推出来：
一个正整数$N$，它可以被分解为若干质因数幂的乘积$p_1^{a_1}*p_2^{a_2}*…*p_k^{a_k}$，换句话说，这些$p_1,p_2,…,p_k$都可以整除$N$，那么对于与$N$互质的数$D$，这些质数就都不能整除$D$了。因此，可以求出在$1\sim N$中随意选出一个数，它不能被上述质数中的任意一个整除，这个事件的概率有多大，然后用$N$乘上这个概率值，就可以得到欧拉函数$\phi(N)$的值了。

首先，这个事件可以视作多个互相独立的事件$A_i$（从$1\sim N$中选出一个数，使其不被质数$p_i$整除）的交集，而考研数学的概率论中有这么一条关于独立事件$A,B$的规律：$P(AB)=P(A)*P(B)$，衍生到$n$个独立事件则可以得出下面的表达式：
$$P(A_1A_2A_3…A_n)=P(A_1)*P(A_2)*P(A_3)*…*P(A_n)={\textstyle \prod_{i=1}^{n}(P(A_i))}$$

然后关注一下其中任意一个事件$A_i$，$1\sim N$的正整数中，能被$p_i$整除的数为$\{ p_i, 2*p_i, 3*p_i, …, m*p_i \}$共$m$个，其中$m=N/p_i$，那么不能被$p_i$整除的数就一共有$N-N/p_i$个，对应$A_i$的概率就为$1-1/p_i$。将所有互相独立的事件$A_i$的概率按照之前的表达式相乘，就可以得出从$1\sim N$中选出一个数，使其不能被所有质数$p_i$整除的概率就是$(1-1/p_1)*(1-1/p_2)*…*(1-1/p_k)$（默认向下取整），最后乘上$N$，并把减号移到分子上，就是$\phi(N)$的表达式：
$$\phi(N)=N*\frac{p_1-1}{p_1}*\frac{p_2-1}{p_2}*…*\frac{p_k-1}{p_k}$$

C++ 代码

/**
 * @brief 欧拉函数（即1~n中与n互质的数的个数）
 * @param n 上限
 * @return 函数值（已定义）
 */
size_t countSmallerCoprimeNumbers(int n) {
    size_t cnt = n;
    for (int i = 2; i <= n; i++) {
        if (n % i == 0) {       //这里一定要提前退出，因为无法整除的话cnt是没有必要计算的
            continue;
        }
        cnt = cnt * (i - 1) / i;
        while (n % i == 0) {
            n /= i;
        }
    }
    if (n > 1) {
        cnt = cnt * (n - 1) / n;
    }
    return cnt;
}