Leetcode 204. Count Primes

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

思路：用一个数组标记小于n的所有数字是否是质数。
外层从2开始遍历到n-1，内层也从2开始遍历，把内外层所有乘积值标记（乘积得到的数肯定不是质数了）。

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

    return res;
}