#include <ctime> #include <cmath> #include <iostream> using namespace std; const int mx = 1000000 + 1; ///在(1,mx)的范围内寻找素数 const int sqrt_mx = (int)sqrt((double)mx); bool vis[mx]; int prime[mx / 10]; ///在mx>65000时建议写成 int prime[mx/10]; /*复杂度O(NlogN)*/ void getPrime(int &cnt) { int i, j; for (i = 2; i <= sqrt_mx; ++i) if (!vis[i]) { prime[cnt++] = i; for (j = i * i; j < mx; j += i) vis[j] = true; } for (; i < mx; ++i) if (!vis[i]) prime[cnt++] = i; } /*复杂度O(N),但常数比较大 O(N)是因为每个合数至多被赋true值一次(每个合数n仅在i=n的最大非平凡因子时被赋值) 以12为例,在原来的算法中,valid[12]在i=2和i=3时均被赋值为true 而在此算法中,valid[12]只在i=6时被赋值(6为12的最大非平凡因子) (PS:n的非平凡因子指不为1和n的因子) */ void linear_getPrime(int &cnt) { int i, j; for (i = 2; i < mx; ++i) { if (!vis[i]) prime[cnt++] = i; for (j = 0; j < cnt && i * prime[j] < mx; ++j) { vis[i * prime[j]] = true; if (i % prime[j] == 0) break; } } } /* (测试数据因机器而异) C++编译器: mx getPrime() linear_getPrime() 加速比 1e6 12.231ms 9.943ms 1.230 1e7 203.71ms 105.23ms 1.936 1e8 2319.3ms 1086.5ms 2.135 1e9 26762ms 11931ms 2.243 但是,在G++编译器下: mx getPrime() linear_getPrime() 加速比 1e6 4.37ms 6.83ms *0.640 3e6 20.51ms 20.19ms 1.016 1e7 154ms 76.8ms 2.005 1e8 1885ms 815.875ms 2.301 1e9 22258ms 9335ms 2.384 */ void run() { int cnt = 0; getPrime(cnt); //linear_getPrime(cnt); } int main() { int loop = 100; double starttime = clock(); // for (int i = 0; i < loop; ++i) run(); // double endtime = clock(); double usetime = (double)difftime(endtime, starttime) / loop; cout << "runtime:" << usetime << "ms" << endl; return 0; }
结论:对于G++编译器的使用者来说(福利),O(N)的算法仅在mx较大时才有很明显的优化效果