Leetcode 204 Count Primes

Description:

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

Solution 1: close to O(n) time complex.

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