查找数的最大素数的算法

本文介绍了查找数的最大素数的算法的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

计算数字最大素数的最佳方法是什么?

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

找到可整除的最低质数

检查除法结果是否为素数

如果没有，找到下一个最低的

转到2.

我基于这个假设，因为它更容易计算出小的素因数.这是对的吗?我还应该考虑其他什么方法?

我现在意识到，如果有两个以上素数在起作用，我的方法是徒劳的，因为当结果是另外两个素数的乘积时，步骤2失败了，因此需要递归算法.

再次现在我已经意识到它仍然可以工作，因为最后找到的质数必须是最高的质数，因此，对步骤2中非质数结果进行的任何进一步测试都将导致较小的质数

解决方案

实际上，有几种更有效的方法来查找大数的因子(对于较小的数，试法师工作得相当好).

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

二次筛子是最著名的分解长达100位数字的方法.另外，算法的一部分很容易通过并行处理完成.

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

一旦您决定如何将数字分为两个因素，这是我能想到的最快的算法，用于找到数字的最大质数:

创建一个优先级队列，该队列最初存储数字本身.每次迭代时，您从队列中删除最高编号，然后尝试将其分为两个因素(当然，不允许1成为这些因素之一).如果此步骤失败，则该数字为素数，并且您有答案！否则，您将两个因素添加到队列中并重复.

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

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

Find lowest prime number that divides cleanly

Check if result of division is prime

If not, find next lowest

Go to 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?

Edit: 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.

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).

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.

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.

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:

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.