In this Leetcode Count Primes problem solution, we need to Count the number of prime numbers less than a non-negative number, n.

Leetcode Count Primes problem solution


Problem solution in Python.

class Solution:
    def countPrimes(self, n):
        """
        :type n: int
        :rtype: int
        """
        ans = 0
        isPrime = [True for _ in range(n)]
        for i in range(2,n):
            if isPrime[i]:
                ans += 1
                j = 2
                while(i*j < n):
                    isPrime[i*j] = False
                    j += 1
        return ans



Problem solution in Java.

class Solution {
    public int countPrimes(int n) {
        if(n < 3)
            return 0;
        
        boolean[] primes = new boolean[n];
        int count = 1;
        for(int p = 3; p < n; p += 2) {
            if(!primes[p]) {
                count++;
                for(int i = p * 3; i < n; i += p * 2)
                    primes[i] = true;
            }
        }
                
        return count;
    }
}


Problem solution in C++.

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


Problem solution in C.

int countPrimes(int num)
{
        int loop_var;
        bool *array;
        int prime = 0;
        long long temp;
        if(num  <= 2 )
                return 0;
        array = malloc(sizeof(bool)*num);
        while(loop_var < num){
                array[loop_var] = 0;
                loop_var++;
        }
        loop_var = 2;
        for(loop_var = 2; loop_var < num; loop_var++){
                if(array[loop_var])
                        continue;
                temp = (long)loop_var*(long)loop_var;
                prime++;
                while(temp < num){
                        array[temp] = 1;
                        temp  += loop_var;
                }
        }
        return prime;
}