Count Primes

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

Solution: Sieve of Eratosthenes

1. Create a list of consecutive integers from 2 to n: (2, 3, 4, …, n).
2. Initially, let p equal 2, the first prime number.
3. Starting from p, count up in increments of p and mark each of these numbers greater than p itself in the list. These numbers will be 2p, 3p, 4p, etc.; note that some of them may have already been marked.
4. Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this number (which is the next prime), and repeat from step 3.

int countPrimes(int n) {
    vector<bool> prime(n, true);
    prime[0] = false, prime[1] = false;

    for (int i=2; i*i <= n; i++) {
        if (prime[i]) {
            for (int j = i*2; j < n; j += i) {
                prime[j] = false;
            }
        }
    }

    return count(prime.begin(), prime.end(), true);
}