204

這題的做法實在太天才了，雖然已經偷看到解法，還是想寫一下來確定自己有理解他的演算法思路。概念上就是，每碰到一個質數，就把所有這個質數的倍數都砍掉，所以在看到2的時候，就把所有isPrime[2n]都設成True，並把質數的計數器count加上1。依序做到n之後，count的數字就是質數的數量。

class Solution {
public:
    int countPrimes(int n) {
        if (n==0) return 0;

        bool isPrime[n] = {false};
        int count = 0;

        for(int i=2; i<n; i++)
        {
            if(isPrime[i])
                continue;

            count ++;
            for(int j=i; j<n; j=j+i)
                isPrime[j] = true;
        }

        return count;
    }
};