0

13195 的质因数是 5、7、13 和 29。数字 600851475143 的最大质因数是多少？@ http://projecteuler.net/problem=3

我和自己有个协议，如果我不能解决项目欧拉问题，我会理解我能找到的最佳解决方案。我确实写了一个算法，它适用于较小的数字，但对于较大的数字来说效率太低了。所以我用谷歌搜索了Zach Denton 的答案并开始研究它。

这是他的代码：

#!/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 循环中，他为什么使用 asqrt(n + 1)而不是 just sqrt(n)？
  2. sqrt(n + 1)在第一个 while 循环中迭代偶数时， 为什么不使用呢？
  3. 该算法如何设法仅找到主要因素？在我第一次编写的算法中，我有一个单独的测试来检查一个因子是否是素数，但他没有打扰。
4

1 回答 1

2

  1. 我怀疑这+1与不精确有关float（我不确定它是否真的需要，或者只是作者的防御举措）。

  2. 第一个while循环将所有两个因素都排除在n. 我不知道如何sqrt(n + 1)适应那里。

  3. 如果你从小因素到大因素，你会自动排除所有复合候选者。想一想：一旦你因式分解5，你已经自动分解出10,15等等20。无需检查它们是否是质数：到那时n将不能被它们整除。

我怀疑检查素数会破坏原始算法的性能。

于 2013-11-12T11:34:17.507 回答