查看: 1586|回復: 4

關於質數篩法的效率

[複製鏈接]
  • TA的每日心情
    鬱悶
    2015-5-15 22:38
  • 簽到天數: 33 天

    [LV.5]常住居民I

    75

    主題

    302

    帖子

    766

    積分

    版主

    TFcis - 105 附設監工官

    Rank: 7Rank: 7Rank: 7

    積分
    766

    台南一中資訊社程式設計達人 - 2014

    發表於 2014-12-13 23:17:22 | 顯示全部樓層 |閱讀模式

    趕快加入我們來參與討論吧!

    您需要 登錄 才可以下載或查看,沒有帳號?加入我們

    x
    本帖最後由 jd3 於 2014-12-22 13:47 編輯

    我一開始學質數表就從演算法筆記整個抄下來
    久了也用得很習慣了(做到他給出UVA例題前那段)複雜度O(N*loglogN),我不會證
    http://www.csie.ntnu.edu.tw/~u91029/Prime.html

    後來看到這篇
    http://blog.csdn.net/mysword/article/details/5122855
    他說是線性,我還是不會證
    於是我又來實驗效率
    發現在沒優化的情況下沒差多少(如果把演算法筆記裡的 if (!sieve[k])拿掉)

    照著演算法筆記寫的比較容易優化
    我開質數表到1000000000
    實驗了幾個寫法

    (以下雖然寫直接抄下來不過CODE中有加入把質數丟進vector裡的部分)
    1.演算法筆記抄下來後刪去 if (!sieve[k]) 那行
    2.同1 ,直接抄下來
    3.同2 ,外加第一層for的優化(略過3的倍數)

    本機實測(單位:sec)
    1.
    47.433
    44.847
    2.
    19.763
    19.047
    3.
    18.944
    18.633


    第一次的都比較差是因為我開著chrome


    所以啦~
    一開始都不覺得加 if (!sieve[k]) 會變快
    結果真的天差地遠

    如有誤歡迎糾正~~~


    CODE:
    我看放第3個就好了
    3.
    [C++] 純文本查看 復制代碼
    #include<iostream>
    #include<cstdio>
    #include<vector>
    #include<time.h>
    
    #define n 1000000000
    
    using namespace std;
    
    bool nt_prime[n+100];
    vector<int> prime;
    
    int main()
    {
            int st = clock();
            prime.push_back(2);prime.push_back(3);
            for(int i = 6 ; i <= n ; i+=3)
                    nt_prime[i] = true;
            for(int i = 5, ii=2 ; i <= n ; i+=ii, ii=6-ii)
                    if(!nt_prime[i])
                    {
                            prime.push_back(i);
                            for(int k=n/i, j=i*k ; k>=i ; k--,j-=i)
                                    if(!nt_prime[k])
                                            nt_prime[j] = true;
                    }
            
            int ed = clock();
            
            cout << "time = " << (ed-st)/(double)CLOCKS_PER_SEC << endl;
            
            for(int i = 0 ; i < 100 ; i++)
                    printf("%d,", prime[i]);
            
            while(1);
    }



    點評

    jd3
    喔對拼錯了XD  發表於 2014-12-22 13:47
    是打錯了嗎? chrome!=crome  發表於 2014-12-14 10:07
    測試以上code time = 10.629  發表於 2014-12-14 09:01
    <這是個人簽名欄位>
    回復

    使用道具 檢舉

  • TA的每日心情
    開心
    2015-4-12 10:09
  • 簽到天數: 137 天

    [LV.7]常住居民III

    142

    主題

    686

    帖子

    3559

    積分

    邁向天堂

    蘇多門

    Rank: 8Rank: 8

    積分
    3559

    新手達陣台南一中資訊社程式設計達人 - 2014

    發表於 2014-12-14 10:21:54 | 顯示全部樓層
    好驚訝啊!我怎麼覺得加那行應該會更慢,所以是說讀取記憶體資料的速度遠比寫入快嗎?
    蘇多門 domen111
    My Web: https://sites.google.com/site/domenprg/
    回復 支持 反對

    使用道具 檢舉

    您需要登錄後才可以回帖 登入 | 加入我們

    本版積分規則

    快速回覆 返回頂部 返回列表