求助，程序逻辑看不太懂

• Z时代
• 2024-03-03
• 分类：IT

能请各位帮我解释一下这个程序的数学原理吗 ？看不太懂。谢谢。程序的功能是找出最简分数的个数。
如n = 15，找出分母为15且分子小于15的最简分数有8个 1/15, 2/15, 4/15, 7/15, 8/15, 11/15, 13/15, 14/15
比如在返回值之前做的运算是10-2=8，其中的10和2分别表示什么含义呢？
再次感谢！!

def proper_fractions(n):
    phi = n > 1 and n
    for p in range(2, int(n ** .5) + 1):
        if not n % p:
            phi -= phi // p
            while not n % p:
                n //= p
    if n > 1:
        phi -= phi // n
    return phi

回答：

这题本质上是求欧拉函数的值，请参考 https://zh.wikipedia.org/wiki...

其中， 形如

for p in range(2, sqrt(n) + 1)
    while n % p == 0:
        n //= p
    ...

是常见的因式分解算法。

回答：

搜索关键词"xx以内的所有质数", 完全是同一道题

以上是 求助，程序逻辑看不太懂 的全部内容， 来源链接： utcz.com/p/937701.html