素数的求解逐步改进
我的注释都写在代码里面了,就不在赘述了!如果有任何疑问欢迎留言
参考博客:
1.位操作总结:http://blog.csdn.net/morewindows/article/details/7354571
2.找素数算法总结:http://blog.csdn.net/hexiios/article/details/4400068
非常感谢上面两篇博客的仁兄,致谢!
尤其是读了位操作的那篇文章,写的非常好,希望各位都可以一次尝试哈,没准给你的程序增加一个亮点
2的总结也很好,我只是在它的基础上在详细的给了些注释,如果有不懂的地方就好理解了!
?
1.基础补习
什么是合数?什么是素数?百度一下你就知道
?
有一个重要的性质:任何一个合数一定可以表示成若干个素数之积。
如:4 = 2 * 2,6 = 2 * 3,12 = 2 * 2 * 3。也就是说,合数N一定是小于N的某个(或若干)素数的整数倍,反之,如果N不是任何比它小的素数的倍数,则N必然是素数。
这个性质就决定了下面的算法基本思想
?
?
2.检查是否是素数(这个是从基本概念出发的检测算法)
主要的改进就是检测的范围缩小从0---sqrt(n)
?
?
?
?
6,厄拉多塞筛算法改进版
由于对于5来说,最大的缺憾就是利用了辅助数组,那么我们可以减少空间,反正都只是存0,1,为什么不用位来存储呢?这样就大大的减少了空间的浪费了!
首先看看一个为操作的事例:
?
?在下面的算法中就是利用了上面的操作,只要去看看我第一个链接,里面更详细!
?
?
??