项目欧拉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项目来说已经足够了.

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