[Leetcode]07/09 [Hash]Count Primes

/* No hashMap here @@ Time:O(n^2), Space:O(1) Logic: isPrime:O(n) 1-n check isPrime:O(n)*O(n)=O(n^2) Time:O(nlog(logn)); Space:O(n) Logic: ，Sieve of Eratosthenes step 1. assume all number are prime number step 2. starting from 2, take out all 2*2, 2*3, 2*4...2*X and then take out all 3*2, 3*3, 3*4...3*X step 3. count all isPrime number NOTE: i < Math.sqrt(n) boolean isPrime[] = new boolean[n+1]; */

public class Solution {
    public int countPrimes(int n) {
        // speical case
        if ( n <= 2 )
        {
            return 0;
        }
        boolean isPrime[] = new boolean[n+1];
        // step 1. 
        for (  int i =2; i < n ; i++ )
        {
            isPrime[i] = true;
        }  
        // step 2.
        for ( int i =2; i < Math.sqrt(n); i++ )
        {
            if (isPrime[i])
            {
                for ( int j = i+i; j < n; j=j+i)
                {
                    isPrime[j] = false;
                }
            }
        }
        
        // step3
        int count = 0;
        for ( int i =2; i < n ; i++ )
        {
            if (isPrime[i])
            {
                count++;
            }
        }
        
        return count;
    }
}