Description:
Count the number of prime numbers less than a non-negative number, n
上面的这两个参考内容可以看看，第二个给出了经典的解法，在Java Core讲解BitSet的时候也提到了
不过基本版本和不断改进后的版本时间差距非常大：
第一个基本版本[722ms]：
class Solution { public: int countPrimes(int n) { vector<bool> filter(n + 1, false); int cnt = 0; for (int i=2; i<n; i++) { if (!filter[i]) { cnt++; for (int j=i+i; j < n; j+=i) { filter[j] = true; } } } return cnt; } };
这里选择了i+i作为j的起点，其实i+i是2的倍数已经被前面的循环给置位过了，同理所有小于i的数的倍数也都被置位了，因而直接从i*i开始,[619ms]
class Solution { public: int countPrimes(int n) { vector<bool> filter(n, false); int cnt = 0; int lmt = sqrt(n); for (int i=2; i<n; i++) { if (!filter[i]) { cnt++; if (i > lmt) continue; for (int j=i*i; j < n; j+=i) { filter[j] = true; } } } return cnt; } };
因为质数必然不是偶数，所以外层循环可以只考虑奇数的情况，这样就减少了一半计算量[224ms]
class Solution { public: int countPrimes(int n) { if (n <= 2) return 0; vector<bool> filter(n, false); int cnt = 1; int lmt = sqrt(n); for (int i=3; i<n; i+=2) { if (!filter[i]) { cnt++; if (i > lmt) continue; for (int j=i*i; j < n; j+=i) { filter[j] = true; } } } return cnt; } };
相应的内层循环也可以只考虑奇数的情况，因为偶数的情况肯定在i=2时已经被置位了[140ms]
class Solution { public: int countPrimes(int n) { if (n <= 2) return 0; vector<bool> filter(n, false); int cnt = 1; int lmt = sqrt(n); for (int i=3; i<n; i+=2) { if (!filter[i]) { cnt++; if (i > lmt) continue; for (int j=i*i, step = i << 1; j < n; j+=step) { filter[j] = true; } } } return cnt; } };
把vector换成数组又可以提升不少速度，[41ms]
class Solution { public: int countPrimes(int n) { if (n <= 2) return 0; bool* filter = new bool[n]; for (int i=0; i<n; i++) filter[i] = false; int cnt = 1; int lmt = sqrt(n); for (int i=3; i<n; i+=2) { if (!filter[i]) { cnt++; if (i > lmt) continue; for (int j=i*i, step = i << 1; j < n; j+=step) { filter[j] = true; } } } delete[] filter; return cnt; } };
原文：http://www.cnblogs.com/lailailai/p/4468270.html