204. Count Primes

Description:

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

Solution,

Bottom-up,

Keep an array to track all number from 2 to n. And iterate the array if the number is a prime number, then we mark all the multiplications of it as non-prime number. We only do this for prime number because all the multiples of a non-prime numbers must be multiples of his prime factors  as well, so all of its multiples should be covered already. 

 public int countPrimes(int n) {  
   if(n<=2) return 0;  
    boolean[] isNonPrime=new boolean[n];  
    int count=0;  
    for(int i=2;i<n;i++){  
      if(!isNonPrime[i]){  
        for(int j=i;j<=n/i && i*j<n;j++) isNonPrime[j*i]=true;  
        count++;  
      }  
    }  
    return count;  
   }