1.题目

给定整数 n ，返回所有小于非负整数 n 的质数的数量 。

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

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

示例 3：

输入：n = 1
输出：0

提示：
0 <= n <= 5 * 106

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-primes

2.思路

（1）判断素数法
该思路比较容易想到，即用变量 cnt 记录质数的个数，遍历每一个小于 n 的非负整数，然后依次对其进行判断，如果是质数，则 cnt++，遍历结束后直接返回 cnt 即可。但这样的效率较低，并且在LeetCode中提交运行时会出现运行时间超时的问题！
（2）埃拉托斯特尼筛法(Sieve of Eratosthenes)
其主要思想是把小于根号 n 的所有素数的倍数剔除掉（或者做特殊标记），那么剩下（或为做标记）的数就都是素数。
（3）欧拉筛法
其主要思想是在埃拉托斯特尼筛法的基础上，让每个合数只被它的最小质因子筛选一次，从而达到不重复筛选的目的。

3.代码实现（Java）

//思路1————判断素数法
public int countPrimes(int n) {
    int cnt = 0;
    for (int i = 0; i < n; i++) {
    	//判断 i 是否为质数/素数
        if (isPrime(i)) {
            cnt++;
        }
    }
    return cnt;
}

//判断非负整数 n 是否为素数/质数，若为素数/质数返回true，否则返回false
public boolean isPrime(int n) {
    if (n == 0 || n == 1) {
        return false;
    }
    if (n == 2) {
        return true;
    }
    for (int i = 2; i <= Math.sqrt(n); i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

//思路2————埃拉托斯特尼筛法
public int countPrimes(int n) {
    int cnt = 0;
    //primes[i] == true:表示非负整数 i 是质量/素数
    boolean[] primes = new boolean[n];
    //将primes初始化，假设全部是素数
    Arrays.fill(primes, true);
    //使用埃拉托斯特尼筛法将非素数标记为false
    for (int i = 2; i * i < n; i++) {
        if (primes[i] == true) {
            //将小于根号 n 的所有素数的倍数标记为 false
            for (int j = i * i; j < n; j += i) {
                primes[j] = false;
            }
        }
    }
    for (int i = 2; i < n; i++) {
        if (primes[i] == true) {
            cnt++;
        }
    }
    return cnt;
}

//思路3————欧拉筛法
public static int countPrimes(int n) {
    int cnt = 0;
    int[] primes = new int[n];
    byte[] check = new byte[n];
    for (int i = 2; i < n; i++) {
        if (check[i] == 0) {
            //当前非负整数 i 是素数，将其保存到 primes 中
            primes[cnt++] = i;
        }
        for (int j = 0; j < cnt && i * primes[j] < n; j++) {
            //将数组 prime 里面纪录的素数，升序来当作要标记非素数的最小因子
            check[i * primes[j]] = 1;
            if (i % primes[j] == 0) {
                break;
            }
        }
    }
    return cnt;
}