Count Primes

Description:

Count the number of prime numbers less than a non-negative number, n.

//TLE
class Solution {
private:
    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;
    }
public:
    int coutPrimes(int n) {
        int count = 0;
        for (int i = 1; i < n; i++) {
            if (isPrime(i))
                count++;
        }
        return count;
    }
};

//筛数法
class Solution2 {
public:
    int countPrimes(int n) {
        if (n <= 1) return 0;
        bool* IsPrime = new bool[n];
        for (int i = 2; i < n; i++) {
            IsPrime[i] = true;
        }

        for (int i = 2; i * i < n; i++) {
            if (!IsPrime[i])
                continue;
            for (int j = i * i; j < n; j += i) {
                IsPrime[j] = false;
            }
        }
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (IsPrime[i])
                count++;
        }
        return count;
    }
};