1.Count Prime

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

Solution I (Iterating till √n)

class Solution
{
public:
    bool isPrime(int n)
    {
        int p=0;
        for (int i = 2; i*i<=n; i++)
        {
            int x = n % i;
            if (x == 0)
            {
                p = p + 1;
            }
        }

        if (p == 0)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    
    int countPrimes(int n)
    {

        int s = 0;
        for (int i = 2; i < n; i++)
        {
            if (isPrime(i))
            {
                s = s + 1;
            }
        }

        return s;
    }
};

Time complexity: O(√n)

Prime Sieve Method (Sieve of Eratosthenes)

class Solution
{
public:
    int countPrimes(int n)
    {
        int s = 0;
        vector<bool> v(n + 1);
        for (int i = 2; i < n; i++)
        {
            if (!v[i])
            {
                for (int j = i; j+i <= n; j += i)
                {
                    v[j+i] = true;
                }
            }
        }

        for (int i = 2; i < n; i++)
        {
            if (!v[i])
            {
                s = s + 1;
            }
        }

        return s;
    }
};

Time Complexity : O(n*log(log(n))) Space Complexity : O(n)