204. Count Primes

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

Example:

Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

Runtime: 24 ms, faster than 72.71% of C++ online submissions for Count Primes.

class Solution {
public:
    int countPrimes(int n) {
        if (n < 3) {
            return 0;
        }
        vector<bool> prime(n, true);
        // 1 isn't a prime
        int countCompositeNumber = 1; // count if it isn't a prime
        for (int i = 2; i < sqrt(n); i++) {
            // skip handled value
            if (!prime[i]) {
                continue;
            }
            // product of i (and i is the smallest multiple)
            int j = i * i;
            while (j < n) {
                if (prime[j]) {
                    prime[j] = false;
                    countCompositeNumber++;
                }
                j = j + i;
            }
        }
        // n - 1 is amount of numbers
        return n - 1 - countCompositeNumber;
    }
};