Count Primes

Description:

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

Analyse: start from 2, label 2 * 2, 2 * 3... as false; then move to 3, label 3 * 2, 3 * 3, ...as false; move to 4, since 4 is already labeled as false, go next; move to 5, label 5 * 2, 5 * 3... as false.   After enumarate all numbers, scan to count how many primes in the array. 

Runtime: 489ms

class Solution {
public:
    int countPrimes(int n) {
        vector<bool> primes(n, true);
        
        // label all non-prime numbers
        for (int i = 2; i < n; i++) {
            if (!primes[i]) continue;
            int count = 2;
            while (count * i <= n) {
                primes[(count++) * i] = false;
            }
        }
        
        // count how many primes in the array
        int result = 0;
        for (int i = 2; i < n; i++) {
            if (primes[i]) result++;
        }
        return result;
    }
};