primes - Project Euler 3 - 为什么这种方法有效？

Question

13195 的质因数是 5、7、13 和 29。
数字 600851475143 的最大质因数是多少？

我自己在Project Euler上解决了这个问题，很慢，后来在某人的github账号上找到了这个解决方案。我无法弄清楚它为什么有效。为什么删除了许多因素，等于一个索引？任何见解？

def Euler3(n=600851475143):
    for i in range(2,100000):
        while n % i == 0:
            n //= i
            if n == 1 or n == i:
                return i

Answer 1

此函数通过查找其输入的连续因子来工作。它找到的第一个因子必然是素数。找到一个质因数后，将它从原来的数中除掉，然后继续这个过程。当我们将它们全部分开(留下 1，或当前因子 (i))时，我们得到了最后一个(最大的)。

让我们在这里添加一些跟踪代码:

def Euler3(n=600851475143):
    for i in range(2,100000):
        while n % i == 0:
            n //= i
            print("Yay, %d is a factor, now we should test %d" % (i, n))
            if n == 1 or n == i:
                return i

Euler3()

这个的输出是:

$ python factor.py
Yay, 71 is a factor, now we should test 8462696833
Yay, 839 is a factor, now we should test 10086647
Yay, 1471 is a factor, now we should test 6857
Yay, 6857 is a factor, now we should test 1

诚然，对于一般的解决方案，范围的顶部应该是n的平方根，但是对于python，调用math.sqrt返回的是一个浮点数，所以我认为原来的程序员是在偷偷走捷径。该解决方案通常不起作用，但对于 Euler 项目来说已经足够了。

但算法的其余部分是合理的。