首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > 编程 >

Java 求素数演算

2012-12-27 
Java 求素数运算网络上对求素数之解数不胜数,我在此总结归纳一下,同时对一些编码,加以改进,效率有成倍热提

Java 求素数运算

网络上对求素数之解数不胜数,我在此总结归纳一下,同时对一些编码,加以改进,效率有成倍热提高。


第一种:

?

原理: 6N(+-)1法
?
????? 任何一个自然数,总可以表示成为如下的形式之一: 6N,6N+1,6N+2,6N+3,6N+4,6N+5 (N=0,1,2,…)
????? 显然,当N≥1时,6N,6N+2,6N+3,6N+4都不是素数,只有形如6N+1和6N+5的自然数有可能是素数。所以,? 除了2和3之外, 所有的素数都可以表示成6N±1的形式(N为自然数)。 根据上述分析,我们可以构造另一面筛子,? 只对形如6N±1的自然数进行筛选,这样就可以大大减少筛选的次数,从而进一步提高程序的运行效率和速度。
??????
????? 在程序上,我们可以用一个二重循环实现这一点,外循环i按3的倍数递增,内循环j为0-1的循环,则2(i+j)-1恰好就是形如6N±1的自然数。

?

?

源码:

?

?? 测试结果: num = 50 0000;运行100次取平均值:

?

耗时:376

?

?

?

热点排行