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

Question

查找数字的最大素数因子的算法计算数字中最大素因子的最佳方法是什么？我认为最有效的将是以下内容：找到干净分配的最低素数检查除法结果是否为素数如果没有，找到下一个最低点转到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 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;}

我最近写了一篇博客文章，解释了这个算法的工作原理

我敢说，一种不需要进行素数测试（并且没有筛子构造）的方法比使用那些方法的方法运行得更快。如果是这种情况，这可能是这里最快的算法。