5

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
4

3 回答 3

8

该函数通过查找其输入的连续因子来工作。它找到的第一个因素必然是素数。找到一个素因数后，将其从原始数中除掉，然后继续该过程。当我们将它们全部分开时（留下 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 项目来说已经足够了。

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

于 2012-09-26T15:55:33.417 回答
3

考虑它如何解决 n=20：

iteration i=2
  while true (20 % 2 == 0)
    n = n//2 = 20//2 = 10
    if (n == 1 or n == 2) false
  while true (10 % 2 == 0)
    n = n//2 = 10//2 = 5
    if (n == 1 or n == 2) false
  while false (5 % 2 == 0)
iteration i = 3
  while false (5 % 3 == 0)
iteration i = 4 
  while false (5 % 4 == 0)
iteration i = 5
  while true (5 % 5 == 0)
    n = n//5 = 5//5 = 1
    if (n == 1 or n == 5) true
      return i, which is 5, which is the largest prime factor of 20

它只是删除因子，并且由于它已经删除了多个素因子（while 循环），因此 i 的许多值实际上只是浪费精力。唯一有机会在循环中做某事的 i 值是 i 的素值。n==i 测试涵盖了像 25 这样的数字是素数的平方的情况。范围似乎有限。它不会给出 2 * 的正确答案（100,000 之后的下一个最大素数。

于 2012-09-26T15:59:18.333 回答
1

没有人真正回答过你的问题。for循环i依次测试每个数字。当为时，while循环测试成功；在这种情况下，它会减少，然后通过与or比较来检查它是否完成。测试是一个（而不仅仅是），以防不止一次划分。inni1nwhileifin

虽然很聪明，但这不是通常编写的通过试除法进行整数分解的方式。n如果因子大于 100000 ，它也将不起作用。我在我的博客上有一个解释。这是我的函数版本，它列出了所有的因素，n而不仅仅是最大的：

def factors(n):
    fs = []
    while n % 2 == 0:
        fs += [2]
        n /= 2
    if n == 1:
        return fs
    f = 3
    while f * f <= n:
        if n % f == 0:
            fs += [f]
            n /= f
        else:
            f += 2
    return fs + [n]

此函数2单独处理，然后仅尝试奇数因子。它也没有对因子设置限制，而是在因子大于剩余的平方根时停止n，因为此时n必须是素数。因子按递增顺序插入，因此输出列表中的最后一个因子将是最大的，这就是您想要的。

于 2012-09-26T17:41:56.907 回答