Description:
Count the number of prime numbers less than a non-negative number, n.
計算小於n的非負整數中素數的個數。
素數又稱質數，是指只能被1和它自身相除的自然數。需要注意的是1既不是素數也不是合數。2是最小的素數。
使用判斷一個數是否是素數的函數，那麼這個函數需要進行一輪循環，在給定的小於n中又要進行一輪循環。所以時間復雜度是O(n^2)。
可以對判斷一個數是否是素數的函數進行優化，對於數i，可以只對2到√i之間的數進行判斷，這樣時間復雜度降低到了O(nlogn)。
但是上面的解法在leetcode中還是超時。
於是想是否存在只進行一輪循環的方法，即在遍歷1至n-1一次的過程中記錄下素數的個數，但是後面就不知道怎麼處理。
然後看leetcode中的小提示,發現了一種更優的尋找素數的方法。首先看下面的這個圖：
![這裡寫圖片描述](https://www.aspphp.online/bianchen/UploadFiles_4619/201701/2017012112501012.gif "\")
這個圖其實就道出了這個算法是怎麼進行的。使用一個長度是n的hash表，最開始這個hash表中的所有元素都是沒有被處理的，從2開始遍歷，如果這個元素沒有被處理，那麼將素數的個數加1，然後將2*2,2*3,2*4……2* k（ 2* k < n）標記為已經被處理了的。接著開始處理3，同理將3*2,3*3,3*4…..3*m( 3 * m < n)標記為已被處理了的，接著是4，由於這個元素已經被處理，繼續向後遍歷，這樣一直處理下去。<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4NCjxwPrTT1eK1wMzi1tDT1tLiyra1vcHL0ru49tX7yv274dLns/a74bW81sLOyszitcTQoby8x8mhozwvcD4NCjxwPsG91ta94reot9ax8Mjnz8KjujwvcD4NCjxwcmUgY2xhc3M9"brush:java;">
class Solution {
public:
/*
//解法一：超時
int countPrimes(int n) {
int count=0;
for(int i=2;i<=n;i++)
{
if(isPrime(i))
count++;
}
return count;
}
bool isPrime(int n)
{
if(n==1)
return false;
for(int i=2;i*i<=n;i++)
{
if(n%i==0)
return false;
}
return true;
}
*/
//解法二：
int countPrimes(int n) {
int * mask=new int[n]();//可以在這裡直接對動態數組進行初始化
int count=0;
for(int i=2;i
