1.问题描述

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

示例 1：

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

输入：n = 0
输出：0
示例 3：

输入：n = 1
输出：0

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-primes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2.思路分析

质数即只能被1和他本身所整除的数

• 这道题可以用暴力法进行求解，枚举1——n的所有数 i ，依次判断这个数 i 能否被2——i-1整除，如果能被整除，则continue；如果不能被整除，那么质数的数量加1.
• 求质数相关问题，我们自然而然可以想到两个筛质数的方法——埃式筛法、欧拉筛法（线性筛法），在这个题中，我们暂时只讨论埃式筛法
  • 埃式筛法：枚举2——n范围内的所有数，把该数的倍数全部判定为合数（因为倍数能被该数整除），依次枚举，直到所有合数都以找出，那么剩下的就是质数。

3.代码展示

// 埃式筛法
class Solution {
    public int countPrimes(int n) {
        boolean[] isPrime=new boolean[n+1];
        Arrays.fill(isPrime,true);
        for(int i=2;i*i<n;i++){
            if(isPrime[i]){
                for(int j=i*i;j<n;j+=i){
                    isPrime[j]=false;
                }
            }
        }
        int ans=0;
        for(int i =2;i<n;i++){
            if(isPrime[i])
                ans++;
        }
        return ans;
    }
}