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

Solution: 用boolean[]记录非prime number，每遇到一个prime number, 做乘法，把notPrime[i * j] = true，这样只会就不用再检查

    public int countPrimes(int n) {
        boolean[] notPrime = new boolean[n];
        int count = 0;
        //更好：int upper = 
        for (int i = 2; i < n; i++) {
            if (notPrime[i] == false) {
                count++;
                //要加((long) i) * j <= Integer.MAX_VALUE，否则n很大时会越界 (或者j从2起而不是从i起)
                for (int j = i; ((long) i) * j <= Integer.MAX_VALUE && i*j < n; j++) {
                    notPrime[i * j] = true;
                }
            }
        }

        return count;
    }
    更好：
    int upper = sqrt(n);
    for (int i = 2; i < n; i++) {
        if (notPrime[i] == false) {
            count++;
            if (i > upper) {
                continue;
            }
            for (int j = i; i*j < n; j++) {
                notPrime[i * j] = true;
            }
        }
    }