c語言求素?cái)?shù)問題算法

《c語言求素?cái)?shù)問題算法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、如何求素?cái)?shù)1．自然數(shù)是0，1，2……2．素?cái)?shù)是2，3，5……（不包括1的只能背1和它本身整除的自然數(shù)）?#include#includevoidmain(){inti,j,flag=1;for(i=101;i<200;i++){flag=1;for(j=2;j<=sqrt(200);j++)if(i%j==0){flag=0;break;}if(flag==1)printf("i=%d是素?cái)?shù)",i);}}【1】求10000以內(nèi)的所有素?cái)?shù)。素?cái)?shù)是除了1和它本身之外再不能被其他數(shù)整除的自然數(shù)。由于找不到一個(gè)通項(xiàng)公式來表

2、示所有的素?cái)?shù)，所以對(duì)于數(shù)學(xué)家來說，素?cái)?shù)一直是一個(gè)未解之謎。像著名的哥德巴赫猜想、孿生素?cái)?shù)猜想，幾百年來不知吸引了世界上多少優(yōu)秀的數(shù)學(xué)家。盡管他們苦心鉆研，嘔心瀝血，但至今仍然未見分曉。自從有了計(jì)算機(jī)之后，人們借助于計(jì)算機(jī)的威力，已經(jīng)找到了2216091以內(nèi)的所有素?cái)?shù)。求素?cái)?shù)的方法有很多種，最簡單的方法是根據(jù)素?cái)?shù)的定義來求。對(duì)于一個(gè)自然數(shù)N，用大于1小于N的各個(gè)自然數(shù)都去除一下N，如果都除不盡，則N為素?cái)?shù)，否則N為合數(shù)。但是，如果用素?cái)?shù)定義的方法來編制計(jì)算機(jī)程序，它的效率一定是非常低的，其中有許多地方都值得改進(jìn)。第一，對(duì)于一個(gè)自然數(shù)N，只要能被一個(gè)非1非

3、自身的數(shù)整除，它就肯定不是素?cái)?shù)，所以不必再用其他的數(shù)去除。第二，對(duì)于N來說，只需用小于N的素?cái)?shù)去除就可以了。例如，如果N能被15整除，實(shí)際上就能被3和5整除，如果N不能被3和5整除，那么N也決不會(huì)被15整除。第三，對(duì)于N來說，不必用從2到N一1的所有素?cái)?shù)去除，只需用小于等于√N(yùn)(根號(hào)N)的所有素?cái)?shù)去除就可以了。這一點(diǎn)可以用反證法來證明：如果N是合數(shù)，則一定存在大于1小于N的整數(shù)d1和d2，使得N=d1×d2。如果d1和d2均大于√N(yùn)，則有：N＝d1×d2>√N(yùn)×√N(yùn)＝N。而這是不可能的，所以，d1和d2中必有一個(gè)小于或等于√N(yùn)?；谏鲜龇治觯O(shè)計(jì)算法如

4、下：(1)用2，3，5，7逐個(gè)試除N的方法求出100以內(nèi)的所有素?cái)?shù)。(2)用100以內(nèi)的所有素?cái)?shù)逐個(gè)試除的方法求出10000以內(nèi)的素?cái)?shù)。首先，將2，3，5，7分別存放在a[1]、a[2]、a[3]、a[4]中，以后每求出一個(gè)素?cái)?shù)，只要不大于100，就依次存放在A數(shù)組中的一個(gè)單元中。當(dāng)我們求100—10000之間的素?cái)?shù)時(shí)，可依次用a[1]－a[2]的素?cái)?shù)去試除N，這個(gè)范圍內(nèi)的素?cái)?shù)可以不保存，直接打印?！?】用篩法求素?cái)?shù)。簡單介紹一下厄拉多塞篩法。厄拉多塞是一位古希臘數(shù)學(xué)家，他在尋找素?cái)?shù)時(shí)，采用了一種與眾不同的方法：先將2－N的各數(shù)寫在紙上：在2的上面畫一

5、個(gè)圓圈，然后劃去2的其他倍數(shù)；第一個(gè)既未畫圈又沒有被劃去的數(shù)是3，將它畫圈，再劃去3的其他倍數(shù)；現(xiàn)在既未畫圈又沒有被劃去的第一個(gè)數(shù)是5，將它畫圈，并劃去5的其他倍數(shù)……依次類推，一直到所有小于或等于N的各數(shù)都畫了圈或劃去為止。這時(shí)，表中畫了圈的以及未劃去的那些數(shù)正好就是小于N的素?cái)?shù)。這很像一面篩子，把滿足條件的數(shù)留下來，把不滿足條件的數(shù)篩掉。由于這種方法是厄拉多塞首先發(fā)明的，所以，后人就把這種方法稱作厄拉多塞篩法。在計(jì)算機(jī)中，篩法可以用給數(shù)組單元置零的方法來實(shí)現(xiàn)。具體來說就是：首先開一個(gè)數(shù)組：a[i]，i=1，2，3，…，同時(shí)，令所有的數(shù)組元素都等于下

6、標(biāo)值，即a[i]=i，當(dāng)i不是素?cái)?shù)時(shí)，令a[i]=0。當(dāng)輸出結(jié)果時(shí)，只要判斷a[i]是否等于零即可，如果a[i]=0，則令i=i+1，檢查下一個(gè)a[i]。篩法是計(jì)算機(jī)程序設(shè)計(jì)中常用的算法之一?！?】用6N±1法求素?cái)?shù)。任何一個(gè)自然數(shù)，總可以表示成為如下的形式之一：6N，6N+1，6N+2，6N+3，6N+4，6N+5(N=0，1，2，…)顯然，當(dāng)N≥1時(shí)，6N，6N+2，6N+3，6N+4都不是素?cái)?shù)，只有形如6N+1和6N+5的自然數(shù)有可能是素?cái)?shù)。所以，除了2和3之外，所有的素?cái)?shù)都可以表示成6N±1的形式(N為自然數(shù))。根據(jù)上述分析，我們可以構(gòu)造另一面

7、篩子，只對(duì)形如6N±1的自然數(shù)進(jìn)行篩選，這樣就可以大大減少篩選的次數(shù)，從而進(jìn)一步提高程序的運(yùn)行效率和速度。在程序上，我們可以用一個(gè)二重循環(huán)實(shí)現(xiàn)這一點(diǎn)，外循環(huán)i按3的倍數(shù)遞增，內(nèi)循環(huán)j為0－1的循環(huán)，則2(i+j)-1恰好就是形如6N±1的自然數(shù)。淺析求素?cái)?shù)算法注意:如果沒有特殊說明,以下討論的都是針對(duì)n為素?cái)?shù)時(shí)的時(shí)間復(fù)雜度1.根據(jù)概念判斷:如果一個(gè)正整數(shù)只有兩個(gè)因子,1和p，則稱p為素?cái)?shù).代碼:時(shí)間復(fù)雜度O(n).boolisPrime(intn){if(n<2)returnfalse;for(inti=2;i

8、rnfalse;returntrue;}2.改進(jìn),去掉偶數(shù)的判斷代碼:時(shí)間復(fù)雜度O(n/2),