前言

线性筛质数

什么是质数

参考百度百科：

质数（英文名：Primen）又称素数，是指在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的自然数。

规定 1 既不是质数又不是合数。

如何判断质数

我们如何判断一个数是否是质数呢？根据定义可以显而易见的写出下面的代码：

// x 是不是质数
public static boolean isPrime(int x) {
    // 只需要检查到 sqrt(x) 即可，i <= x / i 可以防止 i * i 溢出
    for (int i = 2; i <= x / i; i++) {
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}

当然也可以将所有的偶数直接排除，因为偶数一定是合数（除了 2 以外）。

public static boolean isPrime(int x) {
    if (x <= 1) { // 1 既不是合数也不是质数
        return false;
    }
    if (x == 2) { // 2 是最小的质数
        return true;
    }
    if ((x & 1) == 0) { // 排除所有偶数
        return false;
    }
    for (int i = 3; i <= x / i; i += 2) {
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}

显然判断一个数 n 是否是质数的时间复杂度是 $O(n)$。

质数筛

接下来我们上难度，要求出 1 ~ n 范围内的所有的质数的累加和、个数或者我们要在短时间内频繁查询某些数是不是质数。

如果使用上面的做法显然时间复杂度为达到 $O(n\sqrt{n})$ 级别，对于大数量来说可能会超时，所以我们要找出更高效的质数筛选算法。

一个比较常规的思路就是对数据进行预处理，比如将给定区间中的质数筛选出来，对于筛选之后的结果就可以很快速的求出累加和、个数，并且也支持频繁的查询。

那么与之相关的巧妙的算法就包括：

• 埃氏筛，时间复杂度是 $O(nlog(logn))$
• 欧拉筛，时间复杂度是 $O(n)$

埃氏筛

首先明确一个结论，对于任意一个 > 1 的正整数 n，它的 x（x > 1）倍只能是合数。

所以，如果我们从小到大考虑每一个数，同时将当前这个数的所有（比自己大的）倍数记为合数，那么一旦遍历完成，没有标记的数就是质数了。

实际上，我们只需要筛到平方根即可，所以实际的遍历范围是 2 ~ sqrt(n)。

// 埃氏筛统计 0 ~ n 范围上的质数累加和
public int ehrlich(int n) {
    // visit[i] 为 true 表示 i 为合数
    // visit[i] 为 false 表示 i 为质数 
    boolean[] visit = new boolean[n + 1];
    for (int i = 2; i <= n / i; i++) {
        if (!visit[i]) {
            for (int j = i * i; j <= n; j += i) {
                visit[j] = true;
            }
        }
    }
    // 此时 visit 数组就记录了 0 ~ n 范围内的质数和合数情况
    // 可以根据需要计算质数的 sum、cnt，快速判断 x 是否是质数（加入 set 即可）
    // 这里我们简单求个和
    int sum = 0;
    for (int i = 2; i <= n; i++) {
        if (!visit[i]) {
            sum += i;
        }
    }
    return sum;
}

当然，如果只是求范围内的质数数量，那么还可以使用 BitSet 进行标记，这样更加节省内存。

public int ehrlich(int n) {
    if (n <= 1) {
        return 0;
    }
    BitSet visit = new BitSet();
    for (int i = 2; i <= n / i; i++) {
        if (!visit.get(i)) {
            for (int j = i * i; j <= n; j += i) {
                visit.set(j);
            }
        }
    }
    // visit 中设置为 1 的就是合数
    return n - visit.cardinality() - 1;
}

欧拉筛

在埃氏筛中，某些合数可能被多次标记，比如 12 会被 2 和 3 标记。

如果可以让每个合数都只被一个最小的质数标记，那么时间复杂度就可以降到 $O(n)$。

// 欧拉筛统计 0 ~ n 范围上的质数累加和
public int euler(int n) {
    // visit[i] true 表示合数
    // visit[i] false 表示质数
    boolean[] visit = new boolean[n + 1];
    // prime 搜集所有的质数，收集的个数是 cnt
    int[] prime = new int[n / 2 + 1];
    int cnt = 0;
    for (int i = 2; i < n; i++) {
        if (!visit[i]) {
            prime[cnt++] = i;
        }
        for (int j = 0; j < cnt; j++) {
            if (i * prime[j] > n) {
                break;
            }
            visit[i * prime[j]] = true;
            if (i % prime[j] == 0) {
                // 表示 i 之前被 prime[j] 筛过了，直接 break
                break;
            }
        }
    }
    // 求累加和
    int sum = 0;
    for (int i = 0; i < cnt; i++) {
        sum += prime[i];
    }
    return sum;
}