计算质数

204. 计数质数

统计所有小于非负整数 n 的质数的数量。

示例:

输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

暴力方法会超时，我们使用厄拉多塞筛法。

该方法的核心是，一个质数的倍数不会是质数。具体来说，2 是质数，那么 4 ，6，8 … 不会是质数。

我们使用一个数组来存储是否为质数的标记。

class Solution {
    public int countPrimes(int n) {
        int count = 0;
        // book 初始化全部为false，将不是质数的下标变为 true
        boolean[] book = new boolean[n];

        for(int i = 2; i < n; i++){
            if(!book[i]){
                ++count;
                //质数 i 的倍数不可能为质数，将其标记为 true
                for(int j = i; j < n; j += i){
                    book[j] = true;
                }
            }
        }
    return count;
    }
}