题目:

计数质数

解法:

申请一个大小为n的boolean 数组, 默认初始化为false. 然后从2开始遍历, 遇到false, 则计数器加一. 凡是2的倍数的数, 都是非质数, 标记为true. 遇到false我们认为其为质数, 否则不是质数. 同上, 即可求得结果.

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