计算数字中最大素数因子的最佳方法是什么?
我认为最有效的将是以下内容:
-
找到干净分割的最低素数
-
检查除法结果是否为素数
-
如果没有,找到下一个最低点
-
转到2 .
我基于这个假设,因为它更容易计算小素因子 . 这是对的吗?我应该研究哪些其他方法?
编辑:我现在已经意识到,如果有超过2个素因子,我的方法是徒劳的,因为当结果是两个其他素数的乘积时,步骤2失败,因此需要递归算法 .
再次编辑:现在我已经意识到这仍然有效,因为最后找到的素数必须是最高的,因此对步骤2的非素数结果的任何进一步测试都会导致较小的素数 .
27 回答
通过“James Wang”在网上找到这个解决方案
实际上,有几种更有效的方法可以找到大数的因子(对于较小的因子,试验分工合理地工作得很好) .
如果输入数字具有非常接近其平方根的两个因子,则一种非常快的方法称为Fermat factorisation . 它利用身份N =(a b)(a - b)= a ^ 2 - b ^ 2,易于理解和实现 . 不幸的是,它一般来说不是很快 .
用于将数字分解为最多100位数的最着名的方法是Quadratic sieve . 作为奖励,部分算法可以通过并行处理轻松完成 .
我听说的另一种算法是Pollard's Rho algorithm . 它一般不如Quadratic Sieve有效,但似乎更容易实现 .
一旦你决定如何将一个数字分成两个因子,这里是我能想到的最快的算法,找到一个数字的最大素数因子:
创建一个最初存储数字本身的优先级队列 . 每次迭代,您从队列中删除最高的数字,并尝试将其分成两个因子(当然,不允许1成为这些因素之一) . 如果此步骤失败,则数字为素数,您就有了答案!否则,将两个因子添加到队列中并重复 .
这是我所知道的最好的算法(在Python中)
在最坏的情况下(当输入是素数时),上述方法在
O(n)
中运行 .EDIT:
以下是评论中建议的
O(sqrt(n))
版本 . 这是代码,再一次 .我的答案基于Triptych,但在其上有很大的改进 . 它基于超过2和3的事实,所有素数都是6n-1或6n 1的形式 .
我最近写了一个blog article来解释这个算法是如何工作的 .
我敢说,一种不需要进行素数测试(并且没有筛子构造)的方法比使用那些方法的方法运行得更快 . 如果是这种情况,这可能是这里最快的算法 .
所有数字都可以表示为素数的乘积,例如:
您只需从2开始,只需继续划分直到结果不是您的数字的倍数即可找到这些:
使用这种方法你不必实际计算任何素数:它们都是素数,基于你已经使用所有前面的数字尽可能多地将数字分解的事实 .
JavaScript代码:
用法示例:
Here is an example of the code:
类似@Triptych的回答也不同 . 在此示例中,不使用列表或字典 . 代码是用Ruby编写的
最简单的解决方案是一对相互递归的函数 .
第一个函数生成所有素数:
以包含2和所有大于2的奇数的列表开头 .
删除所有不是素数的数字 . 也就是说,没有素数因素的数字(除了他们自己) . 见下文 .
第二个函数按递增顺序返回给定数字
n
的素数因子 . 策略是试图将每个可能是其除数的素数除以n
:按递增顺序列出所有素数(见上文) .
设
p
是该列表中的素数,ps
是n/p
的主要因子(参见步骤1) .如果
p
平方大于我们的数字n
,那么n
是素数 . 我们完了 .如果
p
除n
,那么p
是n
的主要因子 . 其他因素是ps
.否则
p
不是n
的主要因素 .n
的最大素数因子是第二个函数给出的最后一个数字 .为了澄清,这里是上面的代码,在Haskell中:
有一些模数测试是超级的,因为如果所有因子2和3都已被删除,则n永远不能除以6 . 你只能允许i的素数,这在其他几个答案中显示 .
你真的可以在这里交织了Eratosthenes的筛子:
首先创建最大为sqrt(n)的整数列表 .
在for循环中标记i的所有倍数,直到新的sqrt(n)为非素数,并使用while循环 .
将i设置为列表中的下一个素数 .
另见this question .
我知道这不是一个快速的解决方案 . 发布希望更容易理解缓慢的解决方案 .
Python迭代方法,从数字中删除所有素数因子
我正在使用算法继续将数字除以当前的Prime因子 .
我在python 3中的解决方案:
输入:
10
输出:5
输入:
600851475143
输出:6857
这是我在c#中的尝试 . 最后一次打印输出是该数字的最大主要因素 . 我检查了它的确有效 .
使用C中的递归计算数字的最大素因子 . 代码的工作原理如下:
这是我快速计算最大素因子的方法 . 它基于以下事实:修改后的
x
不包含非素因子 . 为实现这一目标,我们会在找到因素时立即划分x
. 然后,唯一剩下的就是返回最大因子 . 它已经是素数了 .代码(Haskell):
以下C算法不是最好的算法,但它适用于十亿以下的数字并且速度非常快
Prime factor using sieve :
在我看来,给出的算法的第二步并不是那种有效的方法 . 你没有合理的期望它是素数 .
此外,之前的答案暗示了Eratosthenes的筛子是完全错误的 . 我刚写了两个程序来考虑123456789.一个基于Sieve,一个是基于以下内容:
这个版本比Sieve快90倍 .
问题是,在现代处理器上,操作类型远远少于操作数量,更不用说上面的算法可以在缓存中运行,而Sieve则不能 . Sieve使用大量操作来识别所有复合数字 .
另请注意,我识别出的因素会减少必须测试的空间 .
首先计算存储素数的列表,例如2 3 5 7 11 13 ...
每当你对一个数字进行分解时,使用Triptych的实现,但是迭代这个素数列表而不是自然整数 .
使用Java:
对于
int
值:对于
long
值:这可能并不总是更快,但更乐观的是你找到了一个重要的除数:
N
是你的号码如果是素数那么
return(N)
计算素数直到
Sqrt(N)
按降序排列素数(最大的第一个)
如果
N is divisible by Prime
那么Return(Prime)
编辑:在第3步中,您可以使用Eratosthenes的筛子或阿特金斯筛子或任何您喜欢的筛子,但筛子本身并不会找到最重要的因素 . (这就是为什么我不会选择SQLMenace的帖子作为正式答案......)
我认为将所有可能的素数存储在小于n的位置并且只是遍历它们以找到最大的分数是很好的 . 你可以从prime-numbers.org获得素数 .
当然我假设你的号码不是太大:)
不是最快但是有效!
这是@ Triptych作为发生器提供的相同功能,它也略有简化 .
然后可以使用以下命令找到最大素数:
以及使用以下内容找到的因素列表: