algorithm - 是什么让这个质因数分解如此有效？

Question

我一直在做一些 Project Euler 问题来学习/练习 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其中最大的质因数通过连续去除所有其他因数而只出现一次。对于所有其他数字，上述更正也应使其有效。