埃拉托色尼筛选法，全名Sieve of Eratosthenes，简称埃式筛法。算法基于一项基本性质：任何大于1的自然数，要么本身是质数，要么可以分解为几个质数之积，且这种分解是唯一的。

核心思想

质数的倍数一定不是质数。任何大于1的自然数，要么本身是质数，要么可以分解为几个质数之积，且这种分解是唯一的。

因此我们以每个质数为始，标记其在数据范围内的所有倍数为合数。

优化

1. 在遍历以n为范围的数字时，结束边界设为sqrt(n)。
2. 在以质数i为始筛查时，从i*i开始标记，而不是从i*2开始。因为当i > 2时，i*2肯定已经被素数2给过滤了，避免重复计算。

代码模板

int countPrime(int n) {
    boolean[] isPrim = new boolean[n+1];
    Arrays.fill(isPrim, true);
    
    for (int i = 2; i * i < n; i++) {
        if (isPrim[i]) {
            for (int j = i*i; j < n; j += i) {
                isPrim[j] = false;
            }
        }
    }
    
    int count = 0;
    for (int i = 2; i < n; i++) {
        if (isPrim[i])	count++;
    }
    return count;
}

• 时间复杂度：O(nlognlogn)，证明不需要掌握，知道即可
• 空间复杂的：O(n)，用来标记是否为质数。