的若干最大素因子 [英] 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.

还有一个算法我听说的是波拉德的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屋！