欧拉函数 $ ext{varphi}(n)$ 表示小于等于 $n$ 且与 $n$ 互质的正整数个数。计算方法为质因数分解和容斥原理。若 $n = p^k$，则 $ ext{varphi}(n) = p^{k-1}(p-1)$；若 $n =  ext{prod}_{i=1}^{s}p_i^{k_i}$，则 $ ext{varphi}(n) = n  ext{prod}_{i=1}^s rac{p_i - 1}{p_i}$。欧拉函数具有积性，并可通过线性筛法高效计算。