【id:210】【7分】i. 欧拉函数c

欧拉函数（Euler's totient function）是一个与正整数n有关的函数，表示小于等于n的正整数中与n互质的数的数目，记为φ(n)。其中，互质是指除了1以外没有其他公共因子的两个数。

举个例子，如果n=8，小于等于8的正整数中，有1,3,5,7四个数与8互质，因此φ(8)=4。

欧拉函数的计算方法是通过n的质因数分解式来求得。设n=p1^k1 * p2^k2 * ... * pn^kn，其中p1,p2,...,pn均为不同的质数，则：

φ(n) = n * (1-1/p1) * (1-1/p2) * ... * (1-1/pn)

其中，(1-1/p)表示与p互质的数占p的比例，即有p-1个数与p互质，占比为(1-1/p)。

例如，当n=6时，6=2*3，因此φ(6) = 6 * (1-1/2) * (1-1/3) = 2。

对于质数p，φ(p) = p-1，因为质数与小于它的所有数都互质。

欧拉函数在数论中有广泛的应用，例如RSA公钥加密算法中就用到了欧拉函数。