求约简分数的个数

过去两天我一直在研究这个问题。我觉得我已经危险地接近了；但有些事情不太顺利。希望有一双新的眼睛来审视这一点——接受任何建议。

任务是找到任何分母的完全约化分数的数量。 蛮力在一定程度上有效，但我需要能够找到 10^10 以上的结果。完整的挑战在这里：

https://www.codewars.com/kata/number-of-proper-fractions-with-denominator-d/train/python https://www.codewars.com/kata/number-of-proper-fractions-with-denominator-d/train/python

我的代码当前所在的位置：

def proper_fractions(n):
    if n < 1:
        return 0

    numbers = set(range(int(n * 0.5), 1, -1))
    primes = []
    while numbers:
        p = numbers.pop()
        primes.append(p)
        numbers.difference_update(set(range(p * 2, n + 1, p)))

    counter = n

    for num in primes:
        if n % num == 0:
            counter = counter - (n//num)
            n = n//num
            if num >= (n ** 0.5):
                break

    if n == 1:
        return counter
    elif n > 1:
        return counter - (counter // n)

您需要计算的数字称为欧拉总函数 https://en.wikipedia.org/wiki/Euler%27s_totient_function，数量n之间的互质数1 and n.

如果素数分解n is:

,

其欧拉函数为：

用伪代码计算它的算法：

• φ = 1
• m = n
• For every prime number p less than or equal to sqrt(n):
  • If m divides p:
    • 乘φ by p-1
    • Divide m by p-1
  • While m divides p:
    • 乘φ by p
    • Divide m by p
• If m > 1:
  • // 注意此时m必须是一个质因数n比...更棒sqrt(n)
  • 乘φ by m-1