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

实际上,有几种更有效的方法可以找到大数字的因子(对于较小的因子,试验分工合理地工作得很好).

如果输入数字具有非常接近其平方根的两个因子,则一种非常快的方法称为费马因子分解.它利用身份N =(a + b)(a - b)= a ^ 2 - b ^ 2,易于理解和实现.不幸的是,它一般不是很快.

最常见的分解数字长达100位的方法是Quadratic筛.作为奖励,部分算法可以通过并行处理轻松完成.

我听说的另一种算法是Pollard的Rho算法.它一般不如Quadratic Sieve效率高,但似乎更容易实现.

一旦你决定如何将一个数字分成两个因子,这里是我能想到的最快的算法,找到一个数字的最大素数因子:

创建一个最初存储号码本身的优先级队列.每次迭代,您从队列中删除最高的数字,并尝试将其分成两个因子(当然,不允许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;
}

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

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

JavaScript代码：

'option strict';

function largestPrimeFactor(val, divisor = 2) { 
    let square = (val) => Math.pow(val, 2);

    while ((val % divisor) != 0 && square(divisor) <= val) {
        divisor++;
    }

    return square(divisor) <= val
        ? largestPrimeFactor(val / divisor, divisor)
        : val;
}

用法示例：

let result = largestPrimeFactor(600851475143);

这是代码示例：

类似于@Triptych的答案，但也有所不同。在此示例中，不使用列表或字典。代码是用Ruby编写的

def largest_prime_factor(number)
  i = 2
  while number > 1
    if number % i == 0
      number /= i;
    else
      i += 1
    end
  end
  return i
end

largest_prime_factor(600851475143)
# => 6857