Count Primes

 https://leetcode.com/problems/count-primes/

brute force:

class Solution {
public:
    bool isPrime(int n) {
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
    int countPrimes(int n) {
       int cnt = 0;
        for (int i = 2; i < n; i++) {
            if (isPrime(i) == true) {
                cnt++;
            }
        }
        return cnt;
    }
}; 

Sieve of Eratosthenes

class Solution {
public:
   
    int countPrimes(int n) {
       if(n<2) return 0;
       vector<bool> prime(n+1,true);
        prime[0] = false;        
        prime[1] = false;
        int ans = 0;
        for(int i=2;i*i<=n;i++)
        {
            if(prime[i])
            {
                for(int j=i*i;j<=n;j+=i)
                {
                    prime[j] = false;
                }
            }
        }
        for(int i=2;i<n;i++)
        {
            if(prime[i])
            {
                ans++;
            }
        }
        return ans;
    }
};