204 Count Primes 计数质数

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

详见：https://leetcode.com/problems/count-primes/description/

Java实现：

埃拉托斯特尼筛法：从2开始遍历到根号n，先找到第一个质数2，然后将其所有的倍数全部标记出来，然后到下一个质数3，标记其所有倍数，一次类推，直到根号n，此时数组中未被标记的数字就是质数。

class Solution {

    public int countPrimes(int n) {

        int res=0;

        boolean[] prime=new boolean[n];

        Arrays.fill(prime,true);

        for(int i=2;i<n;++i){

            if(prime[i]){

                ++res;

                for(int j=2;i*j<n;++j){

                    prime[i*j]=false;

                }

            }

        }

        return res;

    }

}

参考：https://www.cnblogs.com/grandyang/p/4462810.html