204. 计数质数

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

        bool * isPrime = new bool[n + 1];
        for (int i = 0; i < n + 1; i++)
        {
            isPrime[i] = true;
        }

        vector<int> prime;

        int res = 0;
        for (int i = 2; i < n; i++)
        {
            if (isPrime[i])
            {
                prime.push_back(i);
            }
            for (int j = 0; j < prime.size() && i * prime[j] < n; j++)
            {
                isPrime[i * prime[j]] = false;
                if (i % prime[j] == 0)
                {
                    break;
                }
            }
        }

        return prime.size();
    }
};