Description

Description:

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

Solution

Basic

注意不能用n / 2来减小遍历范围，比如n = 4的话，如果用n / 2来缩小范围，3就没有被处理。
神奇的地方是，用HashSet会超时，改成array就好了。看来如果array范围可控还是用array比较快。
还要注意题目求的是小于n的个数！

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

Optimized

偶数可以skip
TODO