这个过程的逻辑是什么
What is the logic of this process
我在 SO 中处理 Project Euler; and I found a question 中的一个问题。问题和接受的答案说；
n = 600851475143
i = 2
while i * i < n:
while n%i == 0:
n = n / i
i = i + 1
print (n)
太棒了。我还是不明白这个过程怎么这么快，能在0.00001秒内找到6000亿的最大质因数。我为此尝试了很多方法和代码，过程花了一个多小时..
谁能给我解释一下这段代码的逻辑以及为什么它超快？ while 循环在 Python 中有特殊的位置吗？
fundamental theorem of arithmetic 指出每个大于 1 的整数都可以表示为素数的乘积。例如，数字 2100 可以这样表示：
2 x 2 x 3 x 5 x 5 x 7
我把它排列成最大的质因数在右边，在这个例子中是 7。这个算法所做的是从 2 开始除以 n（即 "removing" 这个因数) 直到没有更多要移除（模 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
然后我们将i增加到3并继续。看看最后我们将如何得到最高的质因数？
第一个while循环的i * i < n（实际上应该是i * i <= n）的原因是因为
if one divisor or factor of a number (other than a perfect square) is greater than its square root, then the other factor will be less than its square root. Hence all multiples of primes greater than the square root of n need not be considered.
来自：http://britton.disted.camosun.bc.ca/jberatosthenes.htm
因此，如果 i 大于 n 的平方根，则意味着所有剩余因子的 "pair" 我们已经找到，低于 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
这向您展示了它的工作原理。
我在 SO 中处理 Project Euler; and I found a question 中的一个问题。问题和接受的答案说；
n = 600851475143
i = 2
while i * i < n:
while n%i == 0:
n = n / i
i = i + 1
print (n)
太棒了。我还是不明白这个过程怎么这么快，能在0.00001秒内找到6000亿的最大质因数。我为此尝试了很多方法和代码，过程花了一个多小时..
谁能给我解释一下这段代码的逻辑以及为什么它超快？ while 循环在 Python 中有特殊的位置吗？
fundamental theorem of arithmetic 指出每个大于 1 的整数都可以表示为素数的乘积。例如，数字 2100 可以这样表示：
2 x 2 x 3 x 5 x 5 x 7
我把它排列成最大的质因数在右边，在这个例子中是 7。这个算法所做的是从 2 开始除以 n（即 "removing" 这个因数) 直到没有更多要移除（模 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
然后我们将i增加到3并继续。看看最后我们将如何得到最高的质因数？
第一个while循环的i * i < n（实际上应该是i * i <= n）的原因是因为
if one divisor or factor of a number (other than a perfect square) is greater than its square root, then the other factor will be less than its square root. Hence all multiples of primes greater than the square root of n need not be considered.
来自：http://britton.disted.camosun.bc.ca/jberatosthenes.htm
因此，如果 i 大于 n 的平方根，则意味着所有剩余因子的 "pair" 我们已经找到，低于 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
这向您展示了它的工作原理。