找到一个数的最大素因数的算法 [英] Algorithm to find Largest prime factor of a number

问题描述

计算一个数的最大质因数的最佳方法是什么?

What is the best approach to calculating the largest prime factor of a number?

我认为最有效的方法如下:

I'm thinking the most efficient would be the following:

1. 找出能彻底整除的最小素数
2. 检查除法结果是否为素数
3. 如果不是，请查找下一个最低值
4. 转到 2.

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

I'm basing this assumption on it being easier to calculate the small prime factors. Is this about right? What other approaches should I look into?

我现在意识到，如果有超过 2 个质因数在起作用，我的方法是徒劳的，因为当结果是其他两个质数的乘积时，第 2 步失败，因此需要递归算法.

I've now realised that my approach is futile if there are more than 2 prime factors in play, since step 2 fails when the result is a product of two other primes, therefore a recursive algorithm is needed.

再次现在我意识到这仍然有效，因为最后找到的质数必须是最高的，因此对步骤 2 中的非质数结果的任何进一步测试都会导致更小的质数.

Edit again: And now I've realised that this does still work, because the last found prime number has to be the highest one, therefore any further testing of the non-prime result from step 2 would result in a smaller prime.

推荐答案

实际上有几种更有效的方法可以找到大数的因数(对于较小的数，尝试除法效果相当好).

Actually there are several more efficient ways to find factors of big numbers (for smaller ones trial division works reasonably well).

如果输入数字有两个非常接近其平方根的因数，则一种非常快的方法被称为 费马分解.它利用恒等式 N = (a + b)(a - b) = a^2 - b^2 并且易于理解和实现.不幸的是，它通常不是很快.

One method which is very fast if the input number has two factors very close to its square root is known as Fermat factorisation. It makes use of the identity N = (a + b)(a - b) = a^2 - b^2 and is easy to understand and implement. Unfortunately it's not very fast in general.

最广为人知的分解最多 100 位数字的方法是 二次筛法.作为奖励，部分算法可以通过并行处理轻松完成.

The best known method for factoring numbers up to 100 digits long is the Quadratic sieve. As a bonus, part of the algorithm is easily done with parallel processing.

我听说过的另一种算法是 Pollard 的 Rho 算法.一般来说，它不如二次筛有效，但似乎更容易实现.

Yet another algorithm I've heard of is Pollard's Rho algorithm. It's not as efficient as the Quadratic Sieve in general but seems to be easier to implement.

一旦你决定了如何将一个数分成两个因子，下面是我能想到的最快的算法来找到一个数的最大质因数:

Once you've decided on how to split a number into two factors, here is the fastest algorithm I can think of to find the largest prime factor of a number:

创建一个优先级队列，它最初存储数字本身.每次迭代，您从队列中删除最高的数字，并尝试将其拆分为两个因子(当然，不允许 1 作为这些因子之一).如果这一步失败了，这个数字就是质数，你就有了答案！否则，您将两个因素添加到队列中并重复.

Create a priority queue which initially stores the number itself. Each iteration, you remove the highest number from the queue, and attempt to split it into two factors (not allowing 1 to be one of those factors, of course). If this step fails, the number is prime and you have your answer! Otherwise you add the two factors into the queue and repeat.

这篇关于找到一个数的最大素因数的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！