质数（素数）是指在大于1的自然数中，除了1和该数自身外，无法被其他自然数整除的数。

大于1的自然数若不是质数，则称为合数。

题目：

204. 计数质数

判断一个数是否是质数

1.朴素枚举法

public boolean isPrime(int x) {
    for (int i = 2; i * i <= x; i++) { // x % i (i > sqrt(x)) 一定不等于0
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}

时间复杂度：$O(\sqrt n)$

空间复杂度：$O(1)$

2.厄拉多塞筛法（素数筛法）

如果$x$是质数，那么大于$x$的$x$的倍数$2x,3x,…$一定不是质数。

用一个标记数组来标记一个数是否是质数，当一个数是质数时，将它所有的倍数都标记为非质数。

// 以找到小于n的所有质数为例
public int countPrimes(int n) {
    int[] flag = new int[n];
    int res = 0;
    Arrays.fill(flag, 1); // 初始化标记数组
    for (int i = 2; i < n; i++) {
        if (flag[i] == 1) {
            res++;
            for (long j = i * i; j < n; j += i) {// 从 i*i开始，且每次加i，这样每次都是i的倍数
                flag[(int)j] = 0;
            }
        }
    }
    return res;
}

时间复杂度：$O(nloglogn)$

空间复杂度：$O(n)$

3.线性筛

只有数据量非常大时，才能显示出优势。

class Solution {
    public int countPrimes(int n) {
        List<Integer> primes = new ArrayList<Integer>();
        int[] isPrime = new int[n];
        Arrays.fill(isPrime, 1);
        for (int i = 2; i < n; ++i) {
            if (isPrime[i] == 1) {
                primes.add(i);
            }
            for (int j = 0; j < primes.size() && i * primes.get(j) < n; ++j) {
                isPrime[i * primes.get(j)] = 0;
                if (i % primes.get(j) == 0) {
                    break;
                }
            }
        }
        return primes.size();
    }
}

时间复杂度：$O(n)$

空间复杂度：$O(n)$