題目：Count Primes
統計1-n的素數的個數。
思路1：
通常的思想就是周遊（0，n）範圍内的所有數，對每個數i再周遊(0,sqrt(i))，每個除一遍來判斷是否為素數，這樣時間複雜度為O(n*sqrt(n))。
具體實作不在貼代碼，過程很簡單，兩重循環就可以解決。但是效率很差，n較大時甚至會花幾分鐘才能跑完。
思路2：
用埃拉特斯特尼篩法的方法來求素數，時間複雜度可以達到O(nloglogn)。
首先開一個大小為n的數組prime[]，從2開始循環，找到一個質數後開始篩選出所有非素數；
篩選方法如下：
1.如果i是素數，則從i*i開始篩選，因為2-i在外循環為2-i的時候已經篩選過了；
2.篩選掉所有i的倍數的數，即：将prime[k*i] = false；（i < k < n/i）
思路并不複雜，網上有先将數組分成奇偶再避開偶數，但是這裡當外循環開始為2時，内循環從2^2=4開始會把所有的偶數篩掉。
/**埃氏篩O(nloglogn)**/
int LeetCode::countPrimes(int n){
if (n < 1)return 0;
vector<bool>prime(n + 1,true);
prime.at(0) = false;
prime.at(1) = false;
int count = 0;
for (size_t i = 2; i < n; i++){
if (prime.at(i)){
++count;
//從i*i開始篩選，應為2*i、3*i在i為2、3時已經被篩選過；這裡是為了篩掉質數i的倍數
for (size_t j = i*i; j <= n; j += i)prime.at(j) = false;
}
}
return count;
} 思路3：
線性歐拉篩，時間複雜度O(n)。
上面的篩選法，仔細想想會發現有的合數被重複篩除，例如30，2*15篩了一次，5*6重複篩除，是以也就有了歐拉線性篩法。
首先，先明确一個條件，任何合數都能表示成一系列素數的積。
然後利用了每個合數必有一個最小素因子，每個合數僅被它的最小素因子篩去正好一次。是以為線性時間。
/**線性歐拉篩O(n)**/
int LeetCode::countPrimes2(int n){
if (n < 1)return 0;
vector<bool>flag(n + 1, true);
vector<int>prime;//儲存所有的素數
flag.at(0) = false;
flag.at(1) = false;
int count = 0;
for (size_t i = 2; i < n; i++){
if (flag.at(i)){//記錄素數的個數
++count;
prime.push_back(i);
}
//任何合數都能表示成一系列素數的積，然後利用了每個合數必有一個最小素因子，每個合數僅被它的最小素因子篩去正好一次。是以為線性時間。
for (size_t j = 0; j < count && i*prime.at(j) < n; j++){
flag.at(i*prime.at(j)) = false;//素數的倍數
if (!(i % prime.at(j)))break;//保證每個數隻被最小素數篩選一次
}
}
return count;
} if (!(i % prime.at(j)))break;//保證每個數隻被最小素數篩選一次
prime數組中的素數是遞增的,當 i 能整除 prime[j]，那麼 i*prime[j+1] 這個合數肯定被 prime[j] 乘以某個數篩掉。
因為i中含有prime[j], prime[j] 比 prime[j+1] 小。接下去的素數同理。是以不用篩下去了。
在滿足i%prme[j]==0這個條件之前以及第一次滿足改條件時,prime[j]必定是prime[j]*i的最小因子。
還不清楚的可以參考一下這篇部落格：http://blog.csdn.net/nk_test/article/details/46242401