是什么让这个质因数分解如此有效？
What makes this prime factorization so efficient?
我一直在为 learn/practice 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
这似乎是所有体面的算法。我用较小的数字在纸上计算过，我可以看到它使数字收敛，但我不明白为什么这个操作会收敛于最大的质因数。
谁能解释一下？
这消除了n所有已知的较小质因数，使n变小，可以更早到达sqrt(n)。这会提高性能，因为您不再需要 运行 数字来计算原始 N 的平方根，比如说如果 n 是一百万，它由 2 和 5 组成，并且对所有已知素数进行天真查询需要检查所有不超过 1000 的素数，将其除以 2 得到 15625，然后除以 5 得到 1（顺便说一下，你的算法将 return 1!要修复，如果您的循环以 n=1 退出，则改为 return i。）有效地将大数分解为两个步骤。但这仅适用于 "common" 数字，它们具有单个高素数分母和一堆较小的素数，但分解一个数字 n=p*q 而 p 和 q 都是素数和接近的素数将无法从这个提升中受益。
n=n/i 行之所以有效，是因为如果您正在寻找除 i 之外的另一个素数，您目前被发现是一个除数，根据素数的定义，结果也可以被那个素数整除。阅读此处：https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic。这也只适用于你的情况，因为你的 i 运行s 从 2 向上，所以你首先除以素数，然后除以它们的复合数。否则，如果你的数字有一个 3 作为最大质数，也可以被 2 整除并且你首先检查 6，你会破坏只除以质数的原则（比如 72，如果你首先除以 6，你最终会得到 2，而答案是 3) 不小心除以最大素数的组合。
在这种情况下，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
只要n中有p1，内部的while就会迭代。因此，在迭代完成后（当 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，其中最大的质因数通过连续删除所有其他因数而只出现一次。对于所有其他数字，上述更正应该也能正常工作。
此算法（修正后）需要 O(max(p2,sqrt(p1))) 步来找到 n 的质因数分解，其中 p1 是最大质因数，p2 是第二大质因数。在重复最大素因子的情况下，p1=p2.
Knuth 和 Trabb Pardo 研究了此函数的行为 "Analysis of a Simple Factorization Algorithm" Theoretical Computer Science 3 (1976) 321-348。他们反对通常的分析，例如计算分解最大为 n 的整数时所采取的平均步数。尽管一些具有大质因数的数字提高了平均值，但在密码学上下文中，可能更相关的是某些百分位数非常低。例如，44.7%的数字满足max(sqrt(p1),p2)<n^(1/3)，1.2%的数字满足max(sqrt(p1),p2)<n^(1/5)。
一个简单的改进是在找到新的质因数后测试余数是否为质数。测试一个数是否为质数非常快。这通过避免 p2 和 sqrt(p1) 之间的试验划分将时间减少到 O(p2)。第二大素数的中位数大小约为 n^0.21。这意味着使用这种对试验除法的改进可以快速（在几个处理器秒内）对许多 45 位数字进行因式分解。相比之下，根据一个模型，对两个素数乘积的 Pollard-rho 分解平均需要 O(sqrt(p2)) 步。
我一直在为 learn/practice 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
这似乎是所有体面的算法。我用较小的数字在纸上计算过，我可以看到它使数字收敛，但我不明白为什么这个操作会收敛于最大的质因数。
谁能解释一下？
这消除了n所有已知的较小质因数，使n变小，可以更早到达sqrt(n)。这会提高性能，因为您不再需要 运行 数字来计算原始 N 的平方根，比如说如果 n 是一百万，它由 2 和 5 组成，并且对所有已知素数进行天真查询需要检查所有不超过 1000 的素数，将其除以 2 得到 15625，然后除以 5 得到 1（顺便说一下，你的算法将 return 1!要修复，如果您的循环以 n=1 退出，则改为 return i。）有效地将大数分解为两个步骤。但这仅适用于 "common" 数字，它们具有单个高素数分母和一堆较小的素数，但分解一个数字 n=p*q 而 p 和 q 都是素数和接近的素数将无法从这个提升中受益。
n=n/i 行之所以有效，是因为如果您正在寻找除 i 之外的另一个素数，您目前被发现是一个除数，根据素数的定义，结果也可以被那个素数整除。阅读此处：https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic。这也只适用于你的情况，因为你的 i 运行s 从 2 向上，所以你首先除以素数，然后除以它们的复合数。否则，如果你的数字有一个 3 作为最大质数，也可以被 2 整除并且你首先检查 6，你会破坏只除以质数的原则（比如 72，如果你首先除以 6，你最终会得到 2，而答案是 3) 不小心除以最大素数的组合。
在这种情况下，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
只要n中有p1，内部的while就会迭代。因此，在迭代完成后（当 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，其中最大的质因数通过连续删除所有其他因数而只出现一次。对于所有其他数字，上述更正应该也能正常工作。
此算法（修正后）需要 O(max(p2,sqrt(p1))) 步来找到 n 的质因数分解，其中 p1 是最大质因数，p2 是第二大质因数。在重复最大素因子的情况下，p1=p2.
Knuth 和 Trabb Pardo 研究了此函数的行为 "Analysis of a Simple Factorization Algorithm" Theoretical Computer Science 3 (1976) 321-348。他们反对通常的分析，例如计算分解最大为 n 的整数时所采取的平均步数。尽管一些具有大质因数的数字提高了平均值，但在密码学上下文中，可能更相关的是某些百分位数非常低。例如，44.7%的数字满足max(sqrt(p1),p2)<n^(1/3)，1.2%的数字满足max(sqrt(p1),p2)<n^(1/5)。
一个简单的改进是在找到新的质因数后测试余数是否为质数。测试一个数是否为质数非常快。这通过避免 p2 和 sqrt(p1) 之间的试验划分将时间减少到 O(p2)。第二大素数的中位数大小约为 n^0.21。这意味着使用这种对试验除法的改进可以快速（在几个处理器秒内）对许多 45 位数字进行因式分解。相比之下，根据一个模型，对两个素数乘积的 Pollard-rho 分解平均需要 O(sqrt(p2)) 步。