Problem Statement

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

Example 1:

Input: n = 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

Problem Link

Count Primes - LeetCode

Reference

Sieve of Eratosthenes - GeeksforGeeks

Code

class Solution {
public:
  
    int countPrimes(int n) {
        if(n==0)
            return 0;
      
        vector<bool> prime(n,true);
        prime[0] = false; 
            prime[1] = false;
        for(int i=0;i<sqrt(n);i++) {
            if(prime[i])
            {
              
                for(int j=i*i;j<n;j+=i)
                    prime[j] = false;
            }
        }
        
        return count(prime.begin(), prime.end(), true);
    }
};
// Time complexity : O(n*log(log(n)))