clueless coding // TODO: be smarter

LeetCode 204. Count Primes: C++ Solution



Problem Statement


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

Function Signature (C++):
  int countPrimes(int n)

Inputs:
  n = 24

Outputs:
  9

The primes are:
  2, 3, 5, 7, 11, 13, 17, 19. 23



TL;DR Code Solution


int countPrimes(int n) {

    vector<bool> sieve(n + 1, false);
    int count = 0;

    for (int i = 2; i < n; i++) {
        if (!sieve[i]) {
            count++;
            for (int j = i; j < n; j += i) {
                sieve[j] = true;
            }
        }
    }

    return count;        

}