欧拉函数

对于正整数$n$,欧拉函数是小于或等于$n$的正整数中与$n$互质的数的数目，记作$\varphi(n)$.
$\varphi(1) = 1$

求n的欧拉值

首先， 欧拉函数是一个积性函数，当$m, n$互质时，$\varphi(mn) =\varphi(m)*\varphi(n)$

根据唯一分解定理知 $n = p_1^{a_1} * p_2^{a_2} * … *p_x ^ {a_x}$

因此 $\varphi(n) = \varphi(p_1^{a_1}) * … *\varphi(p_x^{a_x})$

对于任意一项 $\varphi(p_s^{a _s}) = p_s^{a_s} - p_s^{({a_s} - 1)}$

从定义出发 $\varphi(p_s^{a_s})$等于小于或等于$p_s^{a_s}$的正整数中与$p_s^{a_s}$互质的数的数目

从$1$到$p_s^{a_s}$中共有$p_s^{a_s}$个数字

其中与$p_s^{a_s}$不互质的有$p_s, 2p_s, …, {p_s}^{{a_s}- 1} * p_s$ ,共${p_s}^{ a_s - 1}$项

所以 $\varphi(p_s^{a_s})$ = $p_s^{a_s}$ - ${p_s}^{{a_s}- 1} = p_s^{a_s} * (1 - \frac {1}{p_s})$
因此

$$\varphi(n) = \varphi(p_1^{a_1}) * … *\varphi(p_x^{a_x})$$

$$= (p_1^{a_1} - {p_1}^{{a_1}- 1}) * … * (p_x^{a_x} - {p_x}^{{a_x}- 1})$$

$$= p_1^{a_1} * (1 - \frac {1}{p_1}) * p_2^{a_2} * (1 - \frac {1}{p_2}) * …* p_x^{a_x} * (1 - \frac {1}{p_x})$$

$$= p_1^{a_1} * p_2^{a_2} * … *p_x ^ {a_x} * (1 - \frac {1}{p_1}) * (1 - \frac {1}{p_2}) * … * (1 - \frac {1}{p_x})$$

$$= n*\prod_{i=1}^x {(1 - \frac{1}{p_i})}$$