猿问
下载APP

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

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

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

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

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

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

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

  4. 转到2。

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

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

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


幕布斯6054654
浏览 569回答 3
3回答

大话西游666

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

冉冉说

这是我所知道的最好的算法(在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

慕神8447489

我的答案是基于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;}我最近写了一篇博客文章,解释了这个算法的工作原理我敢说,一种不需要进行素数测试(并且没有筛子构造)的方法比使用那些方法的方法运行得更快。如果是这种情况,这可能是这里最快的算法。
打开App,查看更多内容
随时随地看视频慕课网APP
我要回答