Count the number of prime numbers less than a non-negative number, n.
Prime Number: A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself.

The most optimal way to find prime numbers less than n is to user “Sieve of Eratosthenes”
This method uses prime numbers less than the square root of n to deplete a table of 1-n, the rest of the table shall be all the prime numbers.

Source

class Solution {
    public int countPrimes(int n) {
        if(n<3) return 0;
        boolean[] np = new boolean[n];
        // the 'np' array records all the numbers from 0-(n-1) where no-primes are True; primes are False
        // beware the problem asks to find the prime numbers less than n
        np[0]=true;
        np[1]=true;
        for(int i=2;i<Math.sqrt(n);i++){
            if(!np[i]){
                for(int j=2;i*j<n;j++){
                    np[i*j]=true;
                }
            }
        }
        int cnt = 0;
        for(int i=0;i<np.length;i++){
            if(!np[i]) cnt++;
        }
        return cnt;
    }
}