为什么 Totient 函数中的变量 `n` 在每个循环中更新？

Question

我一直在努力寻找给定整数 n 的所有可约分数。

例如，如果输入为数字 5，则输出为 4，因为 1/5、2/5、3/5 和 4/5 都是约化分数。 5/5 不是约化分数，因为它可以约化为 1/1。

我在网上找到了一个解决方案（credits:geeksforgeeks），如下所示，但我不明白为什么在while循环中每次都更新n

def phi(n):   
    # Initialize result as n 
    result = n  

    # Consider all prime factors 
    # of n and subtract their 
    # multiples from result 
    p = 2  
    while(p * p <= n): 

        # Check if p is a  
        # prime factor. 
        if (n % p == 0):  

            # If yes, then  
            # update n and result 
            while (n % p == 0): 
                n = int(n / p) 
            result -= int(result / p); 
        p += 1 

    # If n has a prime factor 
    # greater than sqrt(n) 
    # (There can be at-most  
    # one such prime factor) 
    if (n > 1): 
        result -= int(result / n) 
    return result

Answer 1

在 pythontutor

查看这个 link

n 每次 p 是素数时都会更新。这意味着分数的数量可以减少到更小的素数。所以我们可以把n看做是初始请求中的最小质因数。例如，我们可以想到 phi(16)。如果 n 是最小的素数，而 n > 1 则只能存在一个素数——否则它会陷入 while 循环。

希望对您有所帮助！！！

为什么 Totient 函数中的变量 `n` 在每个循环中更新？

Why variable `n` in Totient Function updated in every loop?

python

fractions