Given an integer n, return the number of prime numbers that are strictly less than n.

&nbsp;
Example 1:

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


Example 2:

Input: n = 0
Output: 0


Example 3:

Input: n = 1
Output: 0


&nbsp;
Constraints:


	0 &lt;= n &lt;= 5 * 106


class Solution:
    def countPrimes(self, n: int) -> int:
        # Prerequisite:
        # What is prime number. What are they just the starting. 
        
        truth = [True]*n # making a list of lenght n. And keep all the values as True.
        if n<2: # as 0 & 1 are not prime numbers. 
            return 0
        truth[0], truth[1] = False, False #as we added True in the truth list. So will make false for ) & 1 as they are not prime numbers.
        
        i=2 # As we know 0 & 1 are not prime.
        while i*i<n: # why we are doing it as i*i here is bcz lets say 5*2 = 10 is divisble by 2 as well as 5 so if 10 is already removed why to traverse a value which is already travered once. so in case of n=5 - 5<5. CONCLUSION : i<sqrt(n)
#why we are running the loop till n is bcz question says " prime numbers that are strictly less than n".
            if truth[i] == True:
                for j in range(i*i,n,i): # if we have mutiple of a number in the range of n, we have to remove them as they can be prime. i.e 2 is prime, but its multiple in n = 10 are 4,6,8 they cant be prime. So we will make them false(means not a prime).
                    truth[j]=False
            i += 1 # increasing our iterator.
        return truth.count(True) # will count true value 
        
class Solution {
    public int countPrimes(int n) {
      boolean check[]=new boolean[n];int count=0;
        for(int i=2;i<n;i++){
            if(check[i]==false){
                count++;
                for(int j=i;j<n;j+=i){
                    check[j]=true;
                }
            }
        }
        return count;
    }
}
class Solution {
public:
    int countPrimes(int n) {
        if(n == 0 || n == 1) return 0;
        vector<bool>prime(n,true);
        for(int i = 2; i*i < n; i++){
            if(prime[i]){
                for(int j = i*i; j < n; j += i){
                    prime[j] = false;
                }
            }
        }
        int cnt = 0;
        for(int i = 2; i < n; i++){
            if(prime[i]) cnt++;
        }
        return cnt;
    }
};
function makeSieve(n) {
    let arr = new Array(n+1)
    arr[0] = false;
    arr[1] = false;
    arr.fill(true,2,arr.length);

    for( let i = 2; i*i<n; i++) {
        if(arr[i] === true) {
            for( let j = i*i ; j<=n ;j+=i){
                arr[j] = false;
            }
        }
    }

    let count = 0;

    for(let i = 0; i<n;i++) {
        if(arr[i] == true) {
            count++;
        }
    }
    return count;
}

var countPrimes = function(n) {
    let numberOfPrimes = makeSieve(n)
    return numberOfPrimes;
};
Count Primes