查找数字的最大素数因子的算法

Question

查找数字的最大素数因子的算法

计算数字中最大素因子的最佳方法是什么？

我认为最有效的将是以下内容：

1. 找到干净分配的最低素数

2. 检查除法结果是否为素数

3. 如果没有，找到下一个最低点

4. 转到2。

我基于这个假设，因为它更容易计算小的素因子。这是对的吗？我应该研究哪些其他方法？

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

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

Answer 1

实际上，有几种更有效的方法可以找到大数字的因子（对于较小的因子，试验分工合理地工作得很好）。如果输入数字具有非常接近其平方根的两个因子，则一种非常快的方法称为费马因子分解。它利用身份N =（a + b）（a - b）= a ^ 2 - b ^ 2，易于理解和实现。不幸的是，它一般不是很快。最常见的分解数字长达100位的方法是Quadratic筛。作为奖励，部分算法可以通过并行处理轻松完成。我听说的另一种算法是Pollard的Rho算法。它一般不如Quadratic Sieve效率高，但似乎更容易实现。一旦你决定如何将一个数字分成两个因子，这里是我能想到的最快的算法，找到一个数字的最大素数因子：创建一个最初存储号码本身的优先级队列。每次迭代，您从队列中删除最高的数字，并尝试将其分成两个因子（当然，不允许1成为这些因素之一）。如果此步骤失败，则数字为素数，您就有了答案！否则，将两个因子添加到队列中并重复。

Answer 2

这是我所知道的最好的算法（在Python中）def prime_factors(n):     """Returns all the prime factors of a positive integer"""     factors = []     d = 2     while n > 1:         while n % d == 0:             factors.append(d)             n /= d         d = d + 1     return factors pfs = prime_factors(1000)largest_prime_factor = max(pfs) # The largest element in the prime factor list上述方法在O(n)最坏的情况下运行（当输入是素数时）。编辑：以下是O(sqrt(n))评论中建议的版本。这是代码，再一次。def prime_factors(n):     """Returns all the prime factors of a positive integer"""     factors = []     d = 2     while n > 1:         while n % d == 0:             factors.append(d)             n /= d         d = d + 1         if d*d > n:             if n > 1: factors.append(n)             break     return factors pfs = prime_factors(1000)largest_prime_factor = max(pfs) # The largest element in the prime factor list

Answer 3

我的答案是基于Triptych的，但在其上有很大的改进。它基于超过2和3的事实，所有素数都是6n-1或6n + 1的形式。var&nbsp;largestPrimeFactor;if(n&nbsp;mod&nbsp;2&nbsp;==&nbsp;0){ &nbsp;&nbsp;&nbsp;&nbsp;largestPrimeFactor&nbsp;=&nbsp;2; &nbsp;&nbsp;&nbsp;&nbsp;n&nbsp;=&nbsp;n&nbsp;/&nbsp;2&nbsp;while(n&nbsp;mod&nbsp;2&nbsp;==&nbsp;0);}if(n&nbsp;mod&nbsp;3&nbsp;==&nbsp;0){ &nbsp;&nbsp;&nbsp;&nbsp;largestPrimeFactor&nbsp;=&nbsp;3; &nbsp;&nbsp;&nbsp;&nbsp;n&nbsp;=&nbsp;n&nbsp;/&nbsp;3&nbsp;while(n&nbsp;mod&nbsp;3&nbsp;==&nbsp;0);}multOfSix&nbsp;=&nbsp;6;while(multOfSix&nbsp;-&nbsp;1&nbsp;<=&nbsp;n){ &nbsp;&nbsp;&nbsp;&nbsp;if(n&nbsp;mod&nbsp;(multOfSix&nbsp;-&nbsp;1)&nbsp;==&nbsp;0) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;largestPrimeFactor&nbsp;=&nbsp;multOfSix&nbsp;-&nbsp;1; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;n&nbsp;=&nbsp;n&nbsp;/&nbsp;largestPrimeFactor&nbsp;while(n&nbsp;mod&nbsp;largestPrimeFactor&nbsp;==&nbsp;0); &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;if(n&nbsp;mod&nbsp;(multOfSix&nbsp;+&nbsp;1)&nbsp;==&nbsp;0) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;largestPrimeFactor&nbsp;=&nbsp;multOfSix&nbsp;+&nbsp;1; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;n&nbsp;=&nbsp;n&nbsp;/&nbsp;largestPrimeFactor&nbsp;while(n&nbsp;mod&nbsp;largestPrimeFactor&nbsp;==&nbsp;0); &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;multOfSix&nbsp;+=&nbsp;6;}我最近写了一篇博客文章，解释了这个算法的工作原理我敢说，一种不需要进行素数测试（并且没有筛子构造）的方法比使用那些方法的方法运行得更快。如果是这种情况，这可能是这里最快的算法。