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

素数的求解渐渐改进

2012-08-22 
素数的求解逐步改进我的注释都写在代码里面了,就不在赘述了!如果有任何疑问欢迎留言参考博客:1.位操作总结

素数的求解逐步改进

我的注释都写在代码里面了,就不在赘述了!如果有任何疑问欢迎留言

参考博客:

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,为什么不用位来存储呢?这样就大大的减少了空间的浪费了!

首先看看一个为操作的事例:

?

?在下面的算法中就是利用了上面的操作,只要去看看我第一个链接,里面更详细!

?

?

?

?

热点排行