欧拉函数

对于求gcd(x, y) = d的问题可以转化为gcd(x/d, y/d) = 1的问题
然后套用欧拉函数

下图套用别人的成果，同时给出一定的解释

对于 i 为质数的理解：

1、感性的认知：i 为质数，即 i 与 小于 i 的正整数都互质----> 因此有 i - 1 个数与 i 互质
2、套用公式：
    i 为质数，只有 1 和 自身 两个因数 --> i = i^1， 1不是质数
    phi(i) = i * (1 - 1/i) = i - 1

对于 phi[i * primes[j]]的推论:

不妨设 i 的质因子为 a1, a2, ..., ak
phi[i] = i * (1 - 1/a1) * (1 - 1/a2) * ... *(1 - 1/ak)

i % primes[j] == 0

由 i % primes[j] == 0，知 i 含有质因子 primes[j]
即 i * primes[j] 并没有引入新的质因子
phi[i*primes[j]] = i * primes[j] * (1 - 1/a1) * (1 - 1/a2) * ... *(1 - 1/ak)
                 = primes[j] * i * (1 - 1/a1) * (1 - 1/a2) * ... *(1 - 1/ak)
                 = primes[j] * phi[i]

i % primes[j] != 0

由 i % primes[j] != 0，知 i 不含有质因子 primes[j]
即 i * primes[j] 有引入新的质因子
phi[i*primes[j]] = i * primes[j] * (1 - 1/primes[j)* (1 - 1/a1) * (1 - 1/a2) * ... *(1 - 1/ak)
                 = primes[j] * (1 - 1/primes[j) * i * (1 - 1/a1) * (1 - 1/a2) * ... *(1 - 1/ak)
                 = (primes[j] - 1) * phi[i]

欧拉函数

python 代码

"""
欧拉函数：
求小于或等于N的正整数与其互质的数量
"""
N = 10001111
# 线性筛变量
cnt = 0
primes = [0] * N
st = [0] * N

# 欧拉函数变量
phi = [0] * N

f = [0] * N

def get_primes(n):
    global cnt
    for i in range(2, n+1):
        if st[i] == 0:
            primes[cnt] = i
            cnt += 1
            # i 为质数时，其phi[i] = i - 1
            """
            1、感性的认知：i 为质数，即 i 与 小于 i 的正整数都互质----> 因此有 i - 1 个数与 i 互质
            2、套用公式：
                i 为质数，只有 1 和 自身 两个因数 --> i = i^1
                phi(i) = i * (1 - 1/i) = i - 1 
            """
            phi[i] = i - 1
        j = 0
        while i * primes[j] <= n:
            """
            不妨设 i 的质因子为 a1, a2, ..., ak
            phi[i] = i * (1 - 1/a1) * (1 - 1/a2) * ... *(1 - 1/ak)
            """
            st[i * primes[j]] = 1
            if i % primes[j] == 0:
                # i % primes[j] == 0
                """
                由 i % primes[j] == 0，知 i 含有质因子 primes[j]
                即 i * primes[j] 并没有引入新的质因子
                phi[i*primes[j]] = i * primes[j] * (1 - 1/a1) * (1 - 1/a2) * ... *(1 - 1/ak)
                                 = primes[j] * i * (1 - 1/a1) * (1 - 1/a2) * ... *(1 - 1/ak)
                                 = primes[j] * phi[i]
                """
                phi[i*primes[j]] = phi[i] * primes[j]
                break
            # i % primes[j] != 0
            """
            由 i % primes[j] != 0，知 i 不含有质因子 primes[j]
            即 i * primes[j] 有引入新的质因子
            phi[i*primes[j]] = i * primes[j] * (1 - 1/primes[j)* (1 - 1/a1) * (1 - 1/a2) * ... *(1 - 1/ak)
                             = primes[j] * (1 - 1/primes[j) * i * (1 - 1/a1) * (1 - 1/a2) * ... *(1 - 1/ak)
                             = (primes[j] - 1) * phi[i]
            """
            phi[i*primes[j]] = phi[i] * (primes[j] - 1)
            j += 1
    # 前缀和
    for i in range(1, n+1):
        f[i] = f[i-1] + phi[i]

n = int(input())
get_primes(n)

ans = 0
for i in range(cnt):
    p = primes[i]
    if p > n:
        break
    # 该题对于gcd(x, y)区分顺序，因此乘以2
    #对于每一个n/p都存在gcd(1, 1)=1，因此加1
    ans += 2 * f[n//p] + 1

print(ans)