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