欧拉函数

计算方式证明实现用公式法来求解欧拉函数筛选法求欧拉函数欧拉定理
对正整数 ，欧拉函数 是小于或等于 的正整数中与 互质的数的数目.

计算方式

对 n 进行分解质因数之后有：
那么有：
例如： , 那么 .

证明

欧拉函数的证明用到了容斥原理：
  1. 1-n中有n个数字，
  1. 先减去所有质数的倍数个数
  1. 此时，会重复减去一些数字，比如 15 即是 3 的倍数，又是5的倍数，所以需要加回来
  1. 此时，会重复加回来一些数字，需要再减去
  1. 依次循环
  1. 最后可化解为如上答案

实现

用公式法来求解欧拉函数

先分解质因数，时间复杂度为
然后 累乘 为每一个因子
def get_ola(num):
    # 初始res 为 num
    res = num
    i = 2
    # 分解质因数的模板
    while i <= num // i:
        if num % i == 0:
            while num % i == 0:
                num //= i
            res *= (1 - 1 / i)
        i += 1
    # 最后余下的数字，也可能是质因数
    if num > 1:
        res *= (1-1/num)

    return res

筛选法求欧拉函数

如果要求 1-n 之间所有数字的欧拉函数，若采用上述方法，则时间复杂度为
此处 借鉴 求质数中的线性筛法。
在线性筛法的过程中，顺便把欧拉函数求一边，可将时间复杂度降低为
  • 质数 i 的欧拉函数为 i-1
  • 对于 primes[j] * i 的欧拉函数
    • if i % primes[j] == 0:
        • 回想一下 欧拉的求解公式，只要 有一个质因子P_x，就要乘 (1-1/P_x)，和P_x的次数是无关的。
        不难想象，primes[j] * i 的质因子包含 i 所有的质因子以及质数 。此外，因为 ，即primes[j] 又为 i 的质因子，也就是说 与 拥有相同的质因子。因此后半部分完全相同！
    • if i % primes[j] != 0:
        • 此时， primes[j] 不是 i 的质因子，所以 primes[j] * i 的质因子，包括了i 的所有质因子和 primes[j]。思路同上
 def get_olas(num):
    # 返回 1-num 之间所有数的欧拉函数

    phi = [0] * (num+1)
    phi[1] = 1

    # 质数 筛选 
    st = [False] * (num+1)
    primes = []
    for i in range(2, num+1):
        if st[i] is False:
            primes.append(i)
            # 质数的欧拉函数 为 本身减1
            phi[i] = i-1
        # 遍历所有的质数
        j = 0
        while primes[j] <= num // i:
            st[primes[j] * i] = True

            if i % primes[j] == 0:
                phi[primes[j] * i] = phi[i] * primes[j]
                break
            phi[primes[j] * i ] = phi[i] * (primes[j]-1)
            
            j += 1
    
    return phi

欧拉定理

若 a 与 n 互质，那么有：