欧拉函数

**欧拉函数**是一个数学函数，记作 φ(n)，用于计算给定正整数n之前（包括n本身）与n**互质**的正整数的个数。

两个整数**互质**意味着它们的最大公约数（GCD）为1。

例如，φ(6) = 2，因为1、5是小于等于6的正整数中与6互质的数。

**欧拉函数**的计算公式为：

\[\phi (n) = n * (1 - 1/p^1) * (1 - 1/p^2) * ... * (1 - 1/p^k)\]

其中，\(p^1、p^2、...、p^k\) 是 \(n\) 的所有不同质因数。

欧拉函数在数论中有广泛的应用，如欧拉筛法就是利用欧拉函数的性质来筛选质数的一种算法。