204. Count Primes

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

To verify a number is prime, you need to divide n by all the number less than n, to see if remainder is 0, in this case, for each number you need to calculate in such way, so the total complexity in time is O(n^2).

There is a simple way, for each number less than n, you only need to visit it once to tell is a primer or not

Start with 2, for all the 2k < n, they are not prime, continue to 2, since all number less than 3 is not factor of 3, so 3 is prime, continue to 4, since already visited when 2k, so not, continue this to n.

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

    }
}