algorithm - 是什么让质因数分解如此高效？

Question

我一直在做一些欧拉项目问题来学习/练习 Lua，而我最初快速而肮脏地寻找 n 最大素因数的方法非常糟糕，所以我查了一下一些代码来看看其他人是如何做的(试图理解不同的因式分解方法)。

我遇到了以下内容(最初是用 Python 编写的 - 这是我的 Lua):

function Main()
    local n = 102
    local i = 2
    while i^2 < n do
        while n%i==0 do n = n / i end
        i = i+1
    end
    print(n)
end

这在非常的短时间内(几乎是立即)计算出了巨大的数字。关于该算法，我注意到了一些我无法预测的事情:

• n = n/i

这似乎存在于所有不错的算法中。我已经在纸上用较小的数字计算出来了，我可以看到它使数字收敛，但我不明白为什么这个操作收敛于最大素因数。

谁能解释一下吗？

Answer 1

在本例中，i是主要因子候选者。考虑一下，n由以下素数组成:

n = p1^n1 * p2^n2 * p3^n3

何时 i达到p1 ，声明n = n / i = n / p1删除 p1 的一次出现:

n / p1 = p1^(n-1) * p2^n2 * p3^n3

内在while只要有 p1 就迭代位于n 。因此，迭代完成后(当 i = i + 1 被执行时)，所有出现的 p1已被删除并且:

n' =  p2^n2 * p3^n3

让我们跳过一些迭代，直到 i达到p3 。剩余n那么就是:

n'' = p3^n3

在这里，我们发现代码中的第一个错误。如果n3是 2，那么外部条件不成立，我们仍然是 p3^2 。应该是while i^2 <= n .

和以前一样，内部while删除所有出现的 p3 ，留给我们 n'''=1 。这是第二个错误。应该是while n%i==0 and n>i (不确定 LUA 语法)，它保留最后一次出现的情况。

所以上面的代码适用于所有数字 n通过连续删除所有其他因子，最大的素因子仅出现一次。对于所有其他数字，上述更正也应该使其有效。