为什么python算法中给定数字的最大素数因子有效？ [重复]

Question

这个问题在这里已有答案：

• Algorithm to find Largest prime factor of a number 27回答

我无法理解我在本网站上遇到的以下代码块。它创建了一个函数来找出给定数字的最大素数因子。它给出如下：

def prime_factors(n):
"""Returns all the prime factors of a positive integer"""
factors = []
d = 2
while n > 1:
    while n % d == 0:
        factors.append(d)
        n /= d
    d = d + 1

return factors
pfs = prime_factors(1000)
largest_prime_factor = max(pfs) # The largest element in the prime 

我怀疑prime_factors(n)函数会返回n的因子而不是主要因子，因为while循环只检查d是否是n的因子而不是它是否也应该是素数。

如果我错了，请指出你的逻辑背后的原因。此外，如果我是正确的，那么请简单地提供一个合适的代码块及其背后的逻辑。尽量保持代码尽可能简单。

Answer 1

请注意，在内循环中，n在迭代时除以d。

while n % d == 0:
    factors.append(d)
    n /= d

这意味着，在每次迭代之后，n的新值不可能被d整除。

举一个例子，让我们说n = 3000，它有一个因素15不是素数。然而，因为n首先通过d = 3和d = 5，当d到达15时，n将是一个既不能被3和5整除的数字，所以非素数因子15现在不会通过n % d == 0。

Answer 2

这个功能是正确的，注意第二个while块。它将连续地将给定数字除以d变量，当除法的结果有余数时，它将离开此块并将d增加1，然后它将再次运行。

记住这一点，这个函数会将数字除以2而不留下余数，然后它将移动到下一个不留下余数的数字。最后，结果只包含素数。

它会像这样：

def prime_factors(n):
   factors = []
   d=2
   while n > 1:
     while n % d == 0:
       factors.append(d)
       n /= d
     d += 1
   return factors

print(prime_factors(1000)) # will print [2, 2, 2, 5, 5, 5]