3 回答
TA贡献1817条经验 获得超14个赞
实际上,有几种更有效的方法可以找到大数字的因子(对于较小的因子,试验分工合理地工作得很好)。
如果输入数字具有非常接近其平方根的两个因子,则一种非常快的方法称为费马因子分解。它利用身份N =(a + b)(a - b)= a ^ 2 - b ^ 2,易于理解和实现。不幸的是,它一般不是很快。
最常见的分解数字长达100位的方法是Quadratic筛。作为奖励,部分算法可以通过并行处理轻松完成。
我听说的另一种算法是Pollard的Rho算法。它一般不如Quadratic Sieve效率高,但似乎更容易实现。
一旦你决定如何将一个数字分成两个因子,这里是我能想到的最快的算法,找到一个数字的最大素数因子:
创建一个最初存储号码本身的优先级队列。每次迭代,您从队列中删除最高的数字,并尝试将其分成两个因子(当然,不允许1成为这些因素之一)。如果此步骤失败,则数字为素数,您就有了答案!否则,将两个因子添加到队列中并重复。
TA贡献1877条经验 获得超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
TA贡献1780条经验 获得超1个赞
我的答案是基于Triptych的,但在其上有很大的改进。它基于超过2和3的事实,所有素数都是6n-1或6n + 1的形式。
var largestPrimeFactor;if(n mod 2 == 0){ largestPrimeFactor = 2; n = n / 2 while(n mod 2 == 0);}if(n mod 3 == 0){ largestPrimeFactor = 3; n = n / 3 while(n mod 3 == 0);}multOfSix = 6;while(multOfSix - 1 <= n){ if(n mod (multOfSix - 1) == 0) { largestPrimeFactor = multOfSix - 1; n = n / largestPrimeFactor while(n mod largestPrimeFactor == 0); } if(n mod (multOfSix + 1) == 0) { largestPrimeFactor = multOfSix + 1; n = n / largestPrimeFactor while(n mod largestPrimeFactor == 0); } multOfSix += 6;}
我最近写了一篇博客文章,解释了这个算法的工作原理
我敢说,一种不需要进行素数测试(并且没有筛子构造)的方法比使用那些方法的方法运行得更快。如果是这种情况,这可能是这里最快的算法。
添加回答
举报