Project Euler 3 - 为什么这种方法有效? [英] Project Euler 3 - Why does this method work?

问题描述

13195 的质因数是 5、7、13 和 29.600851475143的最大质因数是多少?

The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143?

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

I solved this problem on Project Euler my own way, which was slow, and then I found this solution on someone's github account. I can't figure out why it works. Why are a number of factors removed, equal to an index? Any insight?

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

推荐答案

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

This function works by finding successive factors of its input. The first factor it finds will necessarily be prime. After a prime factor is found, it is divided out of the original number and the process continues. By the time we've divided them all out (leaving 1, or the current factor (i)) we've got the last (largest) one.

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

Let's add some tracing code here:

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

It is true that for a general solution, the top of the range should have been the square root of n, but for python, calling math.sqrt returns a floating point number, so I think the original programmer was taking a lazy shortcut. The solution will not work in general, but it was good enough for the Euler project.

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

But the rest of the algorithm is sound.

这篇关于Project Euler 3 - 为什么这种方法有效?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！