204. Count Primes

• Difficulty: Easy

• Topics: Hash Table, Math

• Similar Questions:

  • Ugly Number

  • Ugly Number II

  • Perfect Squares

Problem:

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.

Solutions:

class Solution {
public:
    int countPrimes(int n) {
        if (n <= 1) return 0;
        vector<bool> valid(n, true);

        for (int i = 2; i <= sqrt(n); ++i) {
            if (!valid[i]) continue;
            for (int j = i * 2; j < n; j = j + i) {
                valid[j] = false;
            }
        }

        int count = 0;

        for (int i = 2; i < n; ++i) {
            if (valid[i]) ++count;
        }

        return count;
    }
};