# [204\. Count Primes](https://leetcode.com/problems/count-primes/)

:::spoiler Hint

class Solution {
public:
    int countPrimes(int n)
    {
        // If n is less than or equal to 2, there are no prime numbers less than n
        
        // Create a boolean vector to mark prime numbers
        // 0 and 1 are not prime numbers

        // Use the Sieve of Eratosthenes algorithm to mark non-prime numbers
        for ()
        {
            if () // If i is a prime number
            {
                // Mark all multiples of i as non-prime
            }
        }
        
        // Count the number of prime numbers
        for ()
        {
            // Increment count if i is a prime number
        }
        // Return the total count of prime numbers
    }
};

:::

:::spoiler Solution

class Solution {
public:
    int countPrimes(int n)
    {
        if (n <= 2) return 0;
        vector<bool> isPrime(n, true);
        isPrime[0] = isPrime[1] = false;

        for (int i = 2; i * i < n; ++i)
        {
            if (isPrime[i])
            {
                for (int j = i * i; j < n; j += i)
                {
                    isPrime[j] = false;
                }
            }
        }
        
        int res = 0;
        for (int i = 2; i < n; ++i)
        {
            if (isPrime[i]) res++;
        }
        return res;
    }
};

- T: $O(n \cdot \log ( \log n))$
- S: $O(n)$
:::