求一个数的最大素因数的算法

Question

计算一个数的最大素因数的最佳方法是什么？

我认为最有效的方法是：

找出整除的最小质数

检查除法结果是否为质数

如果不是，找到下一个最低的

转到2。

我把这个假设建立在更容易计算小素数因子的基础上。这是正确的吗？我还应该研究哪些其他方法？

编辑:我现在已经意识到，如果有超过2个素数因子在起作用，我的方法是徒劳的，因为当结果是另外两个素数的乘积时，步骤2失败了，因此需要一个递归算法。

再次编辑:现在我意识到这仍然有效，因为最后找到的质数必须是最高的，因此对步骤2的非质数结果的任何进一步测试都将导致较小的质数。

Answer 1

实际上，有几种更有效的方法来寻找大数的因子(对于较小的因子，尝试除法效果相当好)。

如果输入数有两个因子非常接近其平方根，那么一种非常快速的方法被称为费马分解。它利用了单位N= (a + b)(a - b) = a^2 - b^2，并且易于理解和实现。不幸的是，一般来说，它的速度不是很快。

对长达100位的数字进行因式分解的最著名方法是二次筛法。作为一个额外的好处，该算法的一部分很容易通过并行处理来完成。

我听说过的另一个算法是Pollard的Rho算法。一般来说，它不像二次筛子那样有效，但似乎更容易实现。

一旦你决定了如何将一个数分成两个因子，下面是我能想到的找到一个数的最大素因数的最快算法：

创建一个优先级队列，该队列最初存储数字本身。每次迭代，您从队列中删除最大的数字，并尝试将其分成两个因子(当然，不允许1作为这些因子中的一个)。如果这一步失败，这个数就是质数，你就有答案了！否则，将这两个因子添加到队列中并重复。

Answer 2

这是我所知道的最好的算法(在Python中)

上面的方法在最坏的情况下(当输入是质数时)在O(n)中运行。

编辑：

下面是评论中建议的O(sqrt(n))版本。这是代码，再一次。

Answer 3

我的答案是基于Triptych的，但在此基础上改进了很多。它基于这样一个事实，即除了2和3之外，所有质数的形式都是6n-1或6n+1。

我最近写了一篇博客文章，解释了这个算法是如何工作的。

我敢说，一种不需要质数测试(并且没有筛子结构)的方法会比使用这些的方法运行得更快。如果是这样的话，这可能是这里最快的算法。