篩選法求素數(shù)

本文格式為Word版，下載可任意編輯——篩選法求素數(shù)

用篩選法求素數(shù)

質(zhì)數(shù)算法大全，質(zhì)數(shù)算法大全，及C程序?qū)崿F(xiàn)優(yōu)化詳解篩選法三木追風質(zhì)數(shù)的定義一個數(shù)，假使只有1和它本身兩個因數(shù)，這樣的數(shù)叫做質(zhì)數(shù)，又稱素數(shù)。在上文《素數(shù)算法大全，及C程序?qū)崿F(xiàn)優(yōu)化詳解(一)試除法》中我們已經(jīng)探討了求解素數(shù)的一類算法，并且將試除法從最初的低效版本優(yōu)化的高效的V2。那么，還有沒有其它更佳算法呢？這就是下面三藏要和大家探討的內(nèi)容合數(shù)過濾篩選法算法描述：素數(shù)N不能被2~(N-1)間的任何數(shù)整除；反過來看，只要能被2~(N-1)算法描述我們知道，間的任何數(shù)整除的N，都不是素數(shù)。所以我們可以采用一個簡單的排除法：就是對N以內(nèi)的所有數(shù)，只要逐個去除值為2~(N-1)的倍數(shù)的數(shù)，剩下的就是素數(shù)。C語言實現(xiàn)//合數(shù)過濾篩選法Ver1//參數(shù)：n求解n以內(nèi)(包括n)的素數(shù)//返回值：n以內(nèi)素數(shù)個數(shù)intCompositeNumFilterV1(intn){inti,j;//素數(shù)數(shù)量統(tǒng)計intcount=0;//分派素數(shù)標記空間，結(jié)合后文思考為何+1char*flag=(char*)malloc(n+1);//初始化素數(shù)標記for(i=2;i=n;i++)

用篩選法求素數(shù)

{//為什么*(p+i)要寫成flag[i]呢？可讀性更佳爾flag[i]=1;}//寫程序要注意排版和留空，便利閱讀，也可減少出錯幾率//以2~(N-1)為因子過濾合數(shù)for(i=2;in;i++){for(j=2;i*j=n;j++){//i*j是由i,j兩整數(shù)相乘而得，顯然不是素數(shù)flag[i*j]=0;}}//統(tǒng)計素數(shù)個數(shù)for(i=2;i=n;i++){//其實if(flag)就其同樣作用了，但這么寫是有留言的//請參閱《C語言程序設(shè)計常見錯誤剖析及解決之道》一文if(1==flag[i])count++;}//因輸出費時，且和算法核心相關(guān)不大，故略//釋放內(nèi)存，別忘了傳聞中的內(nèi)存泄漏free(flag);returncount;}在上文給出的main函數(shù)中以不同參數(shù)調(diào)用CompositeNumFilterV1函數(shù)，得到執(zhí)行結(jié)果如下：[100000]以內(nèi)素數(shù)個數(shù)：9592,計算用時：15毫秒[1000000]以內(nèi)素數(shù)個數(shù)：78498,計算用時：125毫秒[5000000]以內(nèi)素數(shù)個數(shù)：348513,計算用時：2578毫秒[10000000]以內(nèi)素數(shù)個數(shù)：664579,計算用時：6281毫秒

用篩選法求素數(shù)

注：因程序是非獨占性運行的，所以時間不是完全確切的，但基本能反映實情顯然，比上文中的試除法要快，而且誰都可以看到上例是一個未經(jīng)優(yōu)化的粗陋版本，好多地方是三藏有意采用比較低效做法，為了與后文的優(yōu)化版比較，凸顯優(yōu)化之重要，也為了初學者記住別采用類似低效做法，下面我們開始優(yōu)化之旅優(yōu)化分析上面CompositeNumFilterV1函數(shù)存在的問題有：1.在外層循環(huán)，需要一直執(zhí)行到n-1嗎？不要，由于n/2~n-1間的數(shù)顯然不能整出n2.在內(nèi)層循環(huán)中重復使用i*j顯然是低效的，考慮到計算機中加減運算速度比乘除快，可以考慮變乘法為加法3.在循環(huán)修改flag過程中，其實有好多數(shù)會被重復計算若干次，譬如6=2*3=3*2，會被重復置0，類似操作好多，所以我們得設(shè)法避免或減少flag重復置0據(jù)上述分析，我們可將程序優(yōu)化如下：//合數(shù)過濾篩選法Ver2//參數(shù)：n求解n以內(nèi)(包括n)的素數(shù)//返回值：n以內(nèi)素數(shù)個數(shù)intCompositeNumFilterV2(intn){inti,j;//素數(shù)數(shù)量統(tǒng)計intcount=0;//分派素數(shù)標記空間，明白+1原因了吧，由于浪費了一個flag[0]char*flag=(char*)malloc(n+1);//初始化素數(shù)標記，要高效點咯flag[2]=1;//注意是in不是上例中的i=n了，理由自思for(i=3;in;i++){flag[i++]=1;//偶數(shù)自然不是素數(shù)，直接置0好了flag[i]=0;}//n為奇數(shù)if(n%2!=0)

用篩選法求素數(shù)

{flag[n]=1;}//從3開始filter，由于2的倍數(shù)早在初始化時代就干掉了//到n/2止的理由還要說嗎for(i=3;i=n/2;i++){//i是合數(shù)，請歇著吧，由于您的工作早有您的質(zhì)因子代勞了if(0==flag[i])continue;//從i的2倍開始過濾，變乘法為加法for(j=i+i;j=n;j+=i){flag[j]=0;}}//統(tǒng)計素數(shù)個數(shù)for(i=2;i=n;i++){if(flag[i])count++;}//因輸出費時，且和算法核心相關(guān)不大，故略//釋放內(nèi)存，別忘了傳聞中的內(nèi)存泄漏free(flag);returncount;}再來調(diào)用CompositeNumFilterV2得到執(zhí)行結(jié)果：[100000]以內(nèi)素數(shù)個數(shù)：9592,計算用時：n太小，時間精度不夠[1000000]以內(nèi)素數(shù)個數(shù)：78498,計算用時：31毫秒[5000000]以內(nèi)素數(shù)個數(shù)：348513,計算用時：453毫秒[10000000]以內(nèi)素數(shù)個數(shù)：664579,計算用時：1062毫秒[100000000]以內(nèi)素數(shù)個數(shù)：5761455,計算用時：12973毫秒

用篩選法求素數(shù)

哇哇，比昨天的試除發(fā)快了好多倍，可見算法的威力，值得好好學習，別說學算法沒用咯。上例著那個計算一億以內(nèi)的素數(shù)只要約13秒，應(yīng)當算不錯了，今天是否可以休息了呢？No，我們要追求極限！intCompositeNumFilterV3(intn){inti,j;//素數(shù)數(shù)量統(tǒng)計intcount=0;//分派素數(shù)標記空間，明白+1原因了吧，由于浪費了一個flag[0]char*flag=(char*)malloc(n+1);//干嘛用的，請細心研究下文intmpLen=2*3*5*7*11*13;charmagicPattern[mpLen];//奇怪的代碼，why，思考無法代勞，想！for(i=0;impLen;i++){magicPattern[i++]=1;magicPattern[i++]=0;magicPattern[i++]=0;magicPattern[i++]=0;magicPattern[i++]=1;magicPattern[i]=0;}for(i=4;i=mpLen;i+=5)magicPattern[i]=0;for(i=6;i=mpLen;i+=7)magicPattern[i]=0;for(i=10;i=mpLen;i+=11)magicPattern[i]=0;for(i=12;i=mpLen;i+=13)magicPattern[i]=0;//新的初始化方法,將2,3,5,7,11,13的倍數(shù)全干掉//而且采用memcpy以mpLen長的magicPattern來批量處理intremainder=n%mpLen;char*p=flag+1;char*pstop=p+n-remainder;

用篩選法求素數(shù)

while(ppstop){memcpy(p,magicPattern,mpLen);p+=mpLen;}if(remainder0){memcpy(p,magicPattern,remainder);}flag[2]=1;flag[3]=1;flag[5]=1;flag[7]=1;flag[11]=1;flag[13]=1;//從17開始filter，由于2,3,5,7,11,13的倍數(shù)早被kill了//到n/13止的，哈哈，少了好多吧intstop=n/13;for(i=17;i=stop;i++){//i是合數(shù)，請歇著吧，由于您的工作早有您的質(zhì)因子代勞了if(0==flag[i])continue;//從i的17倍開始過濾intstep=i*2;for(j=i*17;j=n;j+=step){flag[j]=0;}}//統(tǒng)計素數(shù)個數(shù)for(i=2;i=n;i++){if(flag[i])count++;}//因輸出費時，且和算法核心相關(guān)不大，故略

用篩選法求素數(shù)

//釋放內(nèi)存，別忘了傳聞中的內(nèi)存泄漏free(flag);returncount;}再看Com