Count Prime

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

这题初看不难，判断素数只需要判断能否被1或其本身整除（优化之后可以仅判断2, 3, 4 ... sqrt(n)的数整除即可） 但这样判断会超时错误。这时候只能用筛选法 (Sieve of Eeatosthese)

先将p赋值为2，则p的倍数2p, 3p, 4p ... (xp < n) 都不可能为素数，做一个标记 p循环加1 一直到 p < n 的倍数都做一个标记 剩下的都是素数了 (注意0，1 不是素数）

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