这个过程的逻辑是什么

Question

我正在解决Project Euler 中的一个问题；我在 SO 中发现了一个问题。问题和接受的答案说；

n = 600851475143 
i = 2

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

print (n)

这太棒了。我还是不明白这个过程怎么这么快，竟然能在 0.00001 秒内找到 6000 亿的最大质因数。我为此尝试了大量方法和代码，过程耗时超过 1 小时。

谁能向我解释这些代码的逻辑以及为什么它超快？被while循环有Python中一个特殊的地方？

Answer 1

该算术基本定理指出，每一个大于1的整数可以表示为素数的乘积。例如，数字 2100 可以这样表示：

2 x 2 x 3 x 5 x 5 x 7

我已经安排了它，所以最大的质因数在右边，在这种情况下是 7。这个算法正在做的是从 2 开始并除以n（即“删除”那个因数）直到没有更多的要删除（模 0在除法之前，步骤检查它是否可以干净地整除。）

因此，按照代码，我们将有i= 2 和n= 2100，或者

2 x 2 x 3 x 5 x 5 x 7

2100 可以被 2 ( 2100 % 2 == 0)整除，也是因为我们在上面的分解中看到了 2。所以除以 2 得到 1050，或者

2 x 3 x 5 x 5 x 7

继续除以 2，再一次，得到一个不能被 2 整除的数，即 525，或

3 x 5 x 5 x 7

然后我们增加到i3 并继续。看看最后我们将如何得到最高的质因数？

第一个 while 循环的原因i * i < n（确实应该是i * i <= n）是因为

如果一个数的一个除数或因数（完美平方除外）大于其平方根，则另一个因数将小于其平方根。因此，不需要考虑所有大于n平方根的素数倍数。

来自：http : //britton.disted.camosun.bc.ca/jberatosthenes.htm

因此，如果i大于 的平方根n，则意味着所有剩余的因子都有一个我们已经找到的“对”，低于 的平方根n。使用的检查i * i <= n等效但比进行平方根计算更快。

之所以如此之快，而其他蛮力方法如此之慢，是因为这将每个步骤中的数量进行了划分，从而以指数方式减少了需要完成的步骤数量。

要看到这一点，600851475143 的质因数分解是

71 x 839 x 1471 x 6857

如果您修改代码以阅读：

n = 600851475143
i = 2

while i * i <= n:
    while n%i == 0:
        print "Dividing by %d" % i
        n = n / i
    i = i + 1

if n > 1:
    print n

你会看到的：

>>> 
Dividing by 71
Dividing by 839
Dividing by 1471
6857

这表明这正是它的工作方式。