计算数字的最大素数的最佳方法是什么？
我认为最有效的方法如下：
我将这个假设建立在更容易计算小素数的基础上。这是对的吗？我应该研究哪些其他方法？
编辑：我现在意识到，如果有超过 2 个素数在起作用，我的方法是徒劳的，因为当结果是其他两个素数的乘积时，第 2 步失败，因此需要递归算法。
再次编辑：现在我意识到这仍然有效，因为最后找到的素数必须是最高的，因此对第 2 步的非素数结果的任何进一步测试都会导致更小的素数。
实际上，有几种更有效的方法可以找到大数的因子（对于较小的因子，试行工作相当好）。
如果输入数字具有非常接近其平方根的两个因子，则一种非常快的方法称为费马分解。它利用恒等式 N = (a + b)(a - b) = a^2 - b^2 并且易于理解和实现。不幸的是，它通常不是很快。
对长达 100 位的数字进行因式分解的最著名方法是二次筛。作为奖励，部分算法很容易通过并行处理完成。
我听说过的另一种算法是Pollard 的 Rho 算法。它不像一般的二次筛那样有效，但似乎更容易实现。
一旦你决定如何将一个数字分成两个因子，这是我能想到的最快的算法来找到一个数字的最大素因子：
创建一个优先级队列，该队列最初存储数字本身。每次迭代，您从队列中删除最大的数字，并尝试将其分成两个因素（当然，不允许 1 成为这些因素之一）。如果这一步失败，数字是素数，你有答案！否则，您将这两个因素添加到队列中并重复。
