欧拉函数 $ 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}$。欧拉函数具有积性，并可通过线性筛法高效计算。

本文介绍了求素数的线性筛法和快速线性筛法。线性筛法通过假设所有数为素数，逐步筛除合数，效率较高。快速线性筛法避免了重复筛除，几乎达到线性时间复杂度，关键在于利用素数的乘积特性，确保筛除过程的有效性。