试图理解Euler#3项目的解决方案

Question

The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ? @ http://projecteuler.net/problem=3

我和自己有一个协议，如果我不能解决一个项目的问题，我会明白我能找到最好的解决办法。我确实写了一个算法，适用于较小的数字，但效率太低，无法适用于较大的数字。所以我在谷歌上搜索了Zach Denton's答案并开始研究它。你知道吗

这是他的密码：

#!/usr/bin/env python
import math

def factorize(n):
    res = []
    # iterate over all even numbers first.
    while n % 2 == 0:
        res.append(2)
        n //= 2
    # try odd numbers up to sqrt(n)
    limit = math.sqrt(n+1)
    i = 3
    while i <= limit:
        if n % i == 0:
            res.append(i)
            n //= i
            limit = math.sqrt(n+i)
        else:
            i += 2
    if n != 1:
        res.append(n)
    return res

print max(factorize(600851475143))

以下是我自己都搞不清楚的地方：

1. 在第二个while循环中，为什么他使用sqrt(n + 1)而不是仅仅使用sqrt(n)？你知道吗
2. 为什么不在第一个while循环中迭代偶数时也使用sqrt(n + 1)？你知道吗
3. 算法如何只找到素数因子？在我第一次编写的算法中，我有一个单独的测试来检查一个因子是否是素数，但他并不费心。你知道吗

Answer 1

1. 我怀疑+1与float的不精确性有关（我不确定这是否真的是必需的，或者只是作者的一种防御措施）。

2. 第一个while循环因子都是n中的两个。我看不出sqrt(n + 1)怎么能放进去。

3. 如果你从小因素到大因素，你会自动消除所有复合候选人。想想看：一旦你分解出5，你就会自动分解出10、15、20等等。不需要检查它们是否是素数：到那时n就不会被它们整除。

我怀疑检查素性会破坏原始算法的性能。你知道吗