本帖最後由 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.
[mw_shl_code=cpp,true]#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
= true;
for(int i = 5, ii=2 ; i <= n ; i+=ii, ii=6-ii)
if(!nt_prime)
{
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);
while(1);
}[/mw_shl_code]
