素数的几种判断方法和实现

《素数的几种判断方法和实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、BY：LwPS：本来没有决心把这个东西写完的，结果早上写到一半，出去吃个饭，没保存，回来手一抖直接关掉了，好不容易写了一大半了，只能重新写了，坑爹啊，但就是这个插曲，本来还没有决心的我，一下子却坚定了信念，一点要把这个东西写完。就这样开始吧BY：Lee下面，我们重新开始═══════════════════════════════════════════如何判断一个数是否是素数呢═══════════════════════════════════════════也许你会认为这是一个简单的问题，但事实上，世界上任何一个问题，都没有你想象中的那么简单1+1是否等于2，

2、这便是一个简单而又复杂的问题，呵呵。突然想把这个东西换一种风格来写了，就这样扯淡扯下去吧。扯的时候文章中多少有内容来自于网络，没有侵权的意思，如果作者看到还请见谅。═══════════════════════════════════════════下面正式进入正题═══════════════════════════════════════════一、朴素判断素数═══════════════════════════════════════════1.这种方法被誉为笨蛋的做法：intisprime1(intn){if(n<2)return0;//小于2的数就不是质

3、数了，这个不要忽略for(inti=2;i<=n-1;++i){if(n%i==0)return0;//n与所有比n小的数相除，除得尽的话就是合数}return1;//都除不尽，为素数}一个数去除以比它的一半还要大的数，一定除不尽的，这还用判断吗？？很容易发现的，这种方法判断素数，对于一个整数n，需要n-2次判断，时间复杂度是O(n)在n非常大或者测试量很大的时候，这种笨蛋做法肯定是不可取的。BY：Lw2.改进一下下小学生的做法：intisprime2(intn){if(n<2)return0;for(inti=2;i

4、turn0;}return1;}3.再改进一下聪明的小学生的做法intisprime3(intn){if(n<2)return0;for(inti=2;i*i<=n;++i)//for(inti=2;i<=sqrt(n);++i){if(n%i==0)return0;}return1;}对于一个小于n的整数X，如果n不能整除X,则n必定不能整除n/X。反之相同一个明显的优化，就是只要从2枚举到√n即可。因为在判断2的同时也判断了n/2。到√n时就把2到n-1都判断过了。在这里，这个聪明的小学生还用了i*i<=n来代替sqrt（n），这里是避免了调用函数sqrt（），

5、其消耗时间很大，特别是在大量数据测试的时候消耗很明显。这个算法的时间复杂度，与最前面的笨蛋做法就好多了，不过这里好像用sqrt()也没问题啊，，，，这个就不太清楚了。但是做一个测试发现，如果是这样额话，每一次判断都要计算i*i，BY：Lw而如果只调用sqrt()函数的话，只需要计算一次。故还是sqrt()函数好一些啊。对于一个整数N,需要测试√n-1次，所以本算法的时间复杂度O(√n)。4.再改进一下牛逼的小学生的做法intisprime4(intn){if(n<2)return0;if(n==2)return1;for(inti=3;i*i<=n;i+=2)//f

6、or(inti=3;i<=sqrt(n);++i){if(n%1==0)return0;}return1;}最后，来看一下这个牛逼的小学生，确实，对于一个小学生，能够这么牛逼的想到这么多优化，已经很强大了。不过其实没什么必要。。。。。。这里的i+=2，是因为，偶数除了2之外，是不可能是素数的、所以从3开始，直接+2。进一步优化。这个大概就是朴素判断素数方法的最佳优化了。（也许你还有更好的优化）所以，如果是对于一般的素数判断的话，用上面那个代码吧小学生毕业了，到了中学，会有怎样的成长呢？下面来看看中学生们是怎么样判断的。════════════════════════

7、═══════════════════二、埃拉托斯特尼筛选法═══════════════════════════════════════════埃拉托色尼选筛法(theSieveofEratosthenes)简称埃氏筛法，是古希腊数学家埃拉托色尼(Eratosthenes274B.C.～194B.C.)提出的一种筛选法。BY：Lw是针对自然数列中的自然数而实施的，用于求一定范围内的质数，它的容斥原理之完备性条件是p=H~。可参考：http://zh.wikipedia.org/wiki/%E5%9F%83%E6%8B%89%E6%89%98%E6%96%AF%