欧拉函数，也称为欧拉-费马函数（Euler’s totient function），是对正整数的一种数论函数。对于任意正整数n，欧拉函数phi(n)表示小于等于n的正整数中与n互质的数的个数。
具体地，如果p是一个质数，那么满足条件x <= p且gcd(x, p) = 1的x的个数是p-1个；如果n是一个正整数，可以将n分解为p1^a1 * p2^a2 * … * pk^ak的形式，那么phi(n)的值可以计算为phi(n) = (p1-1)x(p1^(a1-1))x(p2-1)x(p2^(a2-1))x…x(pk-1)x(pk^(ak-1))。
使用python计算欧拉函数的代码如下：
def phi(n):
result = n # phi(n)的初值设为n本身
p = 2
while p * p <= n:
if n % p == 0: # p是n的质因数
while n % p == 0:
n /= p # 去掉n中的因子p
result -= result // p # 更新phi(n)
p += 1
if n > 1: # 如果n是质数
result -= result // n
return result
该代码采用了筛法的思想，逐个枚举小于等于n的质数p，去掉n中的因子p，并且更新phi(n)的值。
另外，如果需要快速计算多个正整数的欧拉函数值，可以采用线性筛法的方法，预处理出所有小于等于某个整数N的正整数的欧拉函数值，代码如下：
def get_euler_totients(n):
phi = list(range(n + 1)) # 初始时假设所有数的phi值为它本身
for i in range(2, n + 1):
if phi[i] == i:
for j in range(i, n + 1, i):
phi[j] -= phi[j] // i
return phi
通过这一函数可以快速获取1~N的所有数字的欧拉函数 $.phi(n)$ 的列表。