204. Count Primes

Solution

需要知道prime的倍數一定不是prime，所以建立boolean array紀錄每個數字是否為Prime，當一旦認定他為prime (ture)，那其倍數必定為false。

另外只需判斷到sqrt(n)就可以推論出0~n所有數是否為質數的狀態( 這是數學理論) 可以進一步減少運算。

TimeComplexity : O(n) * O(1/2 + 1/3 + 1/5 + .... 1/LastPrime) = O(nloglog(n)) with sqr(n) optimized : O(sqrt(n)*loglog(n))

 public int countPrimes(int n) {
        if( n <= 1) return 0;
        boolean[] isPrime = new boolean[n];
        Arrays.fill(isPrime, true);
        isPrime[0] = false;
        isPrime[1] = false;
        for(int i = 2; i <= (int)Math.sqrt(n); i++){ // O(sqrt(n))
            if(isPrime[i]){
                for(int j = 2; j*i < n; j++){ //O(n/2 + n/3 + n/5 + ... +n/lastPrime) 
                    isPrime[j*i] = false;
                }
            }
        }
        int count = 0;
        for(boolean p : isPrime){
            if(p) count++;
        }
        return count;
    }