關於質數篩法的效率

jd3

我一開始學質數表就從演算法筆記整個抄下來
久了也用得很習慣了(做到他給出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);
}

domen111

好驚訝啊！我怎麼覺得加那行應該會更慢，所以是說讀取記憶體資料的速度遠比寫入快嗎？