C++求素?cái)?shù)的算法

《C++求素?cái)?shù)的算法》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、求素?cái)?shù)算法注意：下面的代碼均是以C++編寫的。需求一：請實(shí)現(xiàn)一個函數(shù)，對于給定的整型參數(shù)n，該函數(shù)能夠把自然數(shù)中，小于n的質(zhì)數(shù)，從小到大打印出來。比如，當(dāng)n=10，則打印出2357方案1：試除法分析思路：首先我們了解一下素?cái)?shù)的定義，所謂的素?cái)?shù)指如果有一個正整數(shù)p只有兩個因子1和p,則p為素?cái)?shù)。而這里的試除即根據(jù)素?cái)?shù)的定義，比如要判斷自然數(shù)x是否質(zhì)數(shù)，就不斷嘗試小于x且大于1的自然數(shù)，只要有一個能整除，則x是合數(shù)；否則，x是質(zhì)數(shù)。源代碼：#includeusingnamespacestd;//定義一個判斷素?cái)?shù)函數(shù)boolisPrime(intn){if(n<2)re

2、turnfalse;for(inti=2;i>n;//輸出所有的不大于n的素?cái)?shù)for(inti=2;i<=n;i++){if(isPrime(i))cout<

3、不需要從2到n都要遍歷。而是除了2以外，只需要遍歷不大于n的所有奇數(shù)即可。改進(jìn)的角度2：當(dāng)我們判斷一個數(shù)是否為素?cái)?shù)時，試除時只需要從2到n的根號即可判斷是否為素?cái)?shù)。而且除2以外，所有的質(zhì)數(shù)都是奇數(shù)則也就肯定不會被2整除，這樣試除的遍歷又可以不用遍歷偶數(shù)。源代碼：#include#includeusingnamespacestd;//定義一個判斷素?cái)?shù)函數(shù)boolisPrime(intn){if(n<2)returnfalse;if(n==2)returntrue;for(inti=3;i

4、se;returntrue;}intmain(){intn;//輸出不大于n的素?cái)?shù)cout<<"請輸入一個正整數(shù)："<>n;//輸出所有的不大于n的素?cái)?shù)cout<<"2"<

5、不能被9整除......順著這個思路走下去，這些程序員就會發(fā)現(xiàn)：其實(shí)，只要嘗試小于√x的質(zhì)數(shù)即可。而這些質(zhì)數(shù)，恰好前面已經(jīng)算出來了（是不是覺得很妙？）。在具體的算法實(shí)現(xiàn)時，我們借助了一個單鏈表來存儲上一次所有遍歷出來的素?cái)?shù)，順便說一下，這就是算法理論中經(jīng)常提到的：以空間換時間。源代碼：#include#includeusingnamespacestd;classlist{public:intdata;list*next;};voidprime_number(intm,list*L);intmain(){intm;list*L;L=NULL;cout<

6、<"請輸入一個大于2的整數(shù)：";cin>>m;prime_number(m,L);return0;}voidprime_number(intm,list*L){intjudge=0;//用于判斷是否為素?cái)?shù),是值為0，否則為1.if(m<2){cout<<"輸出的m值小了，沒有質(zhì)數(shù)！"<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：篩選法分析思路：估計(jì)很多人把篩法僅僅看成是一種具體的方法。其實(shí)，篩法還是一種很普適的思想。在處理很多復(fù)雜問題的時候，都可以看到篩法的影子。那么，篩法如何求質(zhì)數(shù)的，說起來很簡單：首先，2是公認(rèn)最小的質(zhì)數(shù)，所以，先把所有2的倍數(shù)去掉；然后剩下的那些大于2的數(shù)里面，最小的是3，所以3也是質(zhì)數(shù)；然后把所有3的倍數(shù)都去掉，剩下的那些大于3的數(shù)里面，最小的是5，