C++求素数的算法

《C++求素数的算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、求素数算法注意：下面的代码均是以C++编写的。需求一：请实现一个函数，对于给定的整型参数n，该函数能够把自然数中，小于n的质数，从小到大打印出来。比如，当n=10，则打印出2357方案1：试除法分析思路：首先我们了解一下素数的定义，所谓的素数指如果有一个正整数p只有两个因子1和p,则p为素数。而这里的试除即根据素数的定义，比如要判断自然数x是否质数，就不断尝试小于x且大于1的自然数，只要有一个能整除，则x是合数；否则，x是质数。源代码：#includeusingnamespacestd;//定义一个判断素数函数boolisPrime(intn){if(n<2)re

2、turnfalse;for(inti=2;i>n;//输出所有的不大于n的素数for(inti=2;i<=n;i++){if(isPrime(i))cout<

3、不需要从2到n都要遍历。而是除了2以外，只需要遍历不大于n的所有奇数即可。改进的角度2：当我们判断一个数是否为素数时，试除时只需要从2到n的根号即可判断是否为素数。而且除2以外，所有的质数都是奇数则也就肯定不会被2整除，这样试除的遍历又可以不用遍历偶数。源代码：#include#includeusingnamespacestd;//定义一个判断素数函数boolisPrime(intn){if(n<2)returnfalse;if(n==2)returntrue;for(inti=3;i

4、se;returntrue;}intmain(){intn;//输出不大于n的素数cout<<"请输入一个正整数："<>n;//输出所有的不大于n的素数cout<<"2"<

5、不能被9整除......顺着这个思路走下去，这些程序员就会发现：其实，只要尝试小于√x的质数即可。而这些质数，恰好前面已经算出来了（是不是觉得很妙？）。在具体的算法实现时，我们借助了一个单链表来存储上一次所有遍历出来的素数，顺便说一下，这就是算法理论中经常提到的：以空间换时间。源代码：#include#includeusingnamespacestd;classlist{public:intdata;list*next;};voidprime_number(intm,list*L);intmain(){intm;list*L;L=NULL;cout<

6、<"请输入一个大于2的整数：";cin>>m;prime_number(m,L);return0;}voidprime_number(intm,list*L){intjudge=0;//用于判断是否为素数,是值为0，否则为1.if(m<2){cout<<"输出的m值小了，没有质数！"<data==0){judge=1;break;}p=p->next;}if(judge==0){cout<

7、dl;s=newlist();s->data=i;s->next=L;L=s;}judge=0;}}方案2：筛选法分析思路：估计很多人把筛法仅仅看成是一种具体的方法。其实，筛法还是一种很普适的思想。在处理很多复杂问题的时候，都可以看到筛法的影子。那么，筛法如何求质数的，说起来很简单：首先，2是公认最小的质数，所以，先把所有2的倍数去掉；然后剩下的那些大于2的数里面，最小的是3，所以3也是质数；然后把所有3的倍数都去掉，剩下的那些大于3的数里面，最小的是5，