• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            (轉)素數算法大全,及C程序實現優化詳解 (一) 試除法

            轉自:http://www.doforfun.net/article/20090504/543.htm
            經常有初學者詢問求解N內所有素數(質數)的問題,對此,網上的解答也很多,但很多要么不夠專業,要么只有程序沒有算法解析,所以三藏大廈對此問題做個小結,探討一下求解素數的常見算法,同時給出相應的C語言程序及其解析。為了方便初學者理解,本文將從易到難闡述不同算法,高手可以直接看后面的高效算法

            質數的定義

            一個數,如果只有1和它本身兩個因數,這樣的數叫做質數,又稱素數。 

            試除判斷法

            算法描述:從上述定義可知,素數不能被1和它本身之外的數整除,所以,判斷一個數x是否素數只要看它是否能被2~sqrt(x)間的數整除即可;而求N內所有素數則是循環重復上述過程。

            C語言實現

            #include <time.h>
            #include <malloc.h>
            #define N 100000
            // 簡單試除判斷法 Ver1
            int SimpleDivisionV1(int n)
            {
             int i,j;
             // 素數數量統計
             int count = 0;
             // 分配存放結果的空間
             int* primes = (int*)malloc( sizeof(int)*n );
             
             // 2是素數誰都知道,不算了
             primes[count++] = 2;
             // 循環計算3~n間的數
             for (i=3; i<=n; i++)
             {
              // 為什么是sqrt(i),思考一下
              for (j=2; j<=sqrt(i); j++)
              {
               // i被j整除,顯然不是素數了
               if (i%j == 0) break;
              }
              // i不能被2~sqrt(i)間的數整除,素數也
              if (j > sqrt(i))
              {
               primes[count++] = i;
              }
             }
             
             // 因輸出費時,且和算法核心相關不大,故略
             
             // 釋放內存,別忘了傳說中的內存泄漏
             free(primes);
             
             return count;
            }

            void main()
            {
             int count;
             clock_t start, end;
             // time函數不夠精確,用clock湊合一下吧
             start = clock();
             count = SimpleDivisionV1(N);
             
             end = clock();
             printf("[%d]以內素數個數:%d, 計算用時:%d毫秒\n", N, count, end-start);
             getch(); 
            }

            計算結果:
            [100000]以內素數個數:9592, 計算用時:468毫秒
            [1000000]以內素數個數:78498, 計算用時:10859毫秒
            [5000000]以內素數個數:348513, 計算用時:103560毫秒

            噢噢,算算十萬還行,百萬就10秒多了,而且時間增長很快,這不行,得優化一下!

            優化分析

            仔細研究一下SimpleDivisionV1我們可以發現以下幾個問題:

            1. 在循環條件中重復調用sqrt(i)顯然是比較浪費時間的
            2. 判斷素數,真的需要拿2~sqrt(i)間的所有整數去除嗎?我們知道,合數都可以分解成若干質數,所以只要2~sqrt(i)間的質數不能整除i即可

            根據上面兩點,我們可將SimpleDivisionV1升級為SimpleDivisionV2,如下

             // 簡單試除判斷法 Ver2 
            int SimpleDivisionV2(int n)
            {
             int i, j, k, stop;
             // 素數數量統計
             int count = 0;
             // 分配存放結果的空間
             int* primes = (int*)malloc( sizeof(int)*n );
             
             // 2是素數誰都知道,不算了
             primes[count++] = 2;
             stop = count;
             // 循環計算3~n間的數
             for (i=3; i<=n; i++)
             {
              k = sqrt(i);
              // 在循環條件中重復調用sqrt是低效做法,故引入k
              while (primes[stop] <= k && stop < count)
               stop++;
              // stop干什么用,思考一下
              for (j=0; j<stop; j++)
              {
               if (i%primes[j] == 0) break;
              }
              // i不能被2~sqrt(i)間的素數整除,自然也不能被其他數整除,素數也
              if (j == stop)
              {
               primes[count++] = i;
              }
             }
             
             // 因輸出費時,且和算法核心相關不大,故略
             
             // 釋放內存,別忘了傳說中的內存泄漏
             free(primes);
             
             return count;
            }

            然后將main中調用的函數替換為SimpleDivisionV2,在看一下執行結果:

            [100000]以內素數個數:9592, 計算用時:46毫秒
            [1000000]以內素數個數:78498, 計算用時:546毫秒
            [5000000]以內素數個數:348513, 計算用時:3515毫秒
            [10000000]以內素數個數:664579, 計算用時:8000毫秒

            很開心的看到,經過優化,速度提高了幾十倍,尤其是時間增長曲線的坡度變小了,N值越大,V2函數比V1的效率就越高

            對于試除判斷這種質數算法來說,三藏認為SimpleDivisionV2基本已經接近極限,不大可能有量級上的突破了,有興趣的朋友可以自己進一步優化。初學者除了參看上述例子外,可以嘗試做各種修改及細節優化,也可以將除法變乘法,多加練習是學習編程的好方法。

            雖然,上例中V2已經比V1快了很多了,但隨著N的增大,耗時還是不少,那么我們還有更好的方法嗎?

            posted on 2009-05-14 15:46 小蟲蟲 閱讀(2491) 評論(1)  編輯 收藏 引用

            評論

            # re: (轉)素數算法大全,及C程序實現優化詳解 (一) 試除法 2010-01-26 17:18 ic engineer

            // 循環計算3~n間的數
            for (i=3; i<=n; i++) 可改為 for(i=3; i<=n; i=i+2)
            這樣只計算奇數,少一半的計算量  回復  更多評論   

            <2009年5月>
            262728293012
            3456789
            10111213141516
            17181920212223
            24252627282930
            31123456

            導航

            統計

            常用鏈接

            留言簿(5)

            隨筆分類

            隨筆檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            国内高清久久久久久| 俺来也俺去啦久久综合网| 久久亚洲精品国产精品婷婷| 久久久久久精品久久久久| 精品久久久久久国产潘金莲| 狠狠色综合久久久久尤物| 色欲综合久久躁天天躁| 精品久久777| 亚洲精品无码久久久久sm| 99久久国产免费福利| 亚洲精品白浆高清久久久久久| 99久久精品国产一区二区| 伊人久久大香线蕉综合影院首页| 日韩亚洲欧美久久久www综合网| 思思久久99热只有频精品66| 91久久香蕉国产熟女线看| 久久精品亚洲一区二区三区浴池| 久久久久国产一区二区| 2021久久国自产拍精品| 亚洲AV成人无码久久精品老人| 久久久艹| 精品国产婷婷久久久| 久久国产精品-久久精品| 无码国内精品久久人妻蜜桃| 久久亚洲电影| 国产ww久久久久久久久久| 精品无码久久久久国产| 亚洲精品无码专区久久久 | 亚洲精品无码成人片久久| 久久久久久久亚洲精品| 2021国产成人精品久久| 精品国产91久久久久久久| 久久av无码专区亚洲av桃花岛| 国产色综合久久无码有码| 久久99国产精品久久99小说| 天天综合久久一二三区| 色婷婷噜噜久久国产精品12p | 无码精品久久久天天影视 | 亚洲欧美一区二区三区久久| 久久久青草青青国产亚洲免观| 91麻精品国产91久久久久|