python为什么这个项目Euler#3解决方案有效？

Question

我最近完成了Project Eulerproblem, number 3，上面写着：

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

当我遇到这个问题时，我正在寻找其他人的解决方案。在

n = 600851475143  
i = 2

while i * i < n:
    while n%i == 0:
        n = n / i
    i = i + 1

 print (n)

现在，我知道这个程序是可行的，但我不知道为什么它会起作用。有人能给我解释一下吗？在

Answer 1

这个解决方案是不正确的。在

当n是质数的平方（例如：4，9，25…）时，它失败了，所以解释它的工作原理将是无用的，因为它不起作用。在

Answer 2

所以看看程序，它似乎得到了n的所有素数因子，并返回最大的一个。让我们一次看一行：

while i * i < n:

这段代码一开始看起来像是一个错误，但是当你意识到{}在不断变小时，它就起作用了。程序使用重复除法将n还原为其最大素数因子。在

^{pr2}$

操作n % i返回n / i的剩余部分。所以如果n % i == 0，那么{}的当前值可以均匀地分成{}，即{}是{}的因子。在

n = n / i

在这里，我们不断地将n除以i；我们将继续这样做，直到while条件不再为真。我们需要尽可能多地进行分割，因为这样可以消除任何可能的复合因素。例如，如果给定的数字是24，我们将它除以2三次，最终使n等于3。这消除了任何可能的2的倍数的复合因子。在

i = i + 1

增加我们的数字，然后重复。在

这很有效，因为通过反复使用n = n / i，我们可以从n中连续删除更大的素数因子。我们消除的这些素数越多，n就越小，直到它最终被除1之外的任何东西都不可分割。此时，n等于原始数的最大素数因子，因此我们返回它。在

现在我们的停车条件也变得更有意义了。当n变为素数（最大素数因子）时，就没有{}的值，我们可以得到它是均匀可除的。当i * i大于n-如果你有一个复合数，那么其中一个因子必然是>= n^1/2。在

正如Ionut Hulub所提到的，如果n是任何完美的正方形，则此特定解决方案将失败。为了防止这种情况的发生，您应该同时打印出n和平均除以该数的最大的i。在