求【1，k】中与n互质的数个数

Question

Python如何求【1，k】中与n互质的数的个数，（k,n均为输入的值）

Answer 1

可以使用欧拉函数（Euler's Totient Function）来计算与给定数n互质的数的个数。欧拉函数的定义是对于任意正整数n，欧拉函数φ(n)表示小于或等于n的正整数中与n互质的数的个数。

def euler_totient(k, n):
    phi = k  # 初始化欧拉函数值为k
    p = 2
    while p * p <= k:
        if k % p == 0:  # 如果k能够整除p，表示p是k的质因数
            while k % p == 0:
                k //= p
            phi -= phi // p  # 更新欧拉函数值
        p += 1
    if k > 1:  # 如果k是一个大于sqrt(k)的质数
        phi -= phi // k
    return phi

# 输入k和n的值
k = int(input("请输入k的值："))
n = int(input("请输入n的值："))

# 调用函数计算与n互质的数的个数
result = euler_totient(k, n)

# 输出结果
print("与n互质的数的个数：", result)