素数的 \(6k \pm 1\) 判定方法

任何正整数 \(n\) 都可以表示为 \(6k + r\) 的形式，其中 \(k,r\) 为自然数且 \(r \in [0, 6)\)，我们讨论每一种 \(r\)：

\(r = 0\)：显然有 \(6 | n\)，\(n\) 为合数。
\(r = 1\)：\(n = 6k + 1\) 可能是素数。
\(r = 2\)：\(6k + 2 = 2(3k + 1)\)，在 \(k \ge 1\) 时 \(n\) 为合数。
\(r = 3\)：\(6k + 3 = 3(2k + 1)\)，在 \(k \ge 1\) 时 \(n\) 为合数。
\(r = 4\)：\(6k + 4 = 2(3k + 2)\)，\(n\) 为合数。
\(r = 5\)：\(n = 6k + 5\) 可能是素数。

从上述分类讨论可知：除了 \(2, 3\) 以外，所有素数都可以表示为 \(6k \pm 1\) 的形式，反之，如果 \(n \bmod 6 \neq \pm 1\)，我们就知道 \(n\) 一定不是素数。

常数优化

在刚刚发现的 \(6k\pm1\) 判定的指导下我们就可以对欧拉筛进行常数优化了：

void sieve() {
    tot = 0;
    for (int i = 1; i <= n; i++) v[i] = false;
    for (int i = 2; i <= 5; i++) {
        if (!v[i]) prime[++tot] = i;
        for (int j = 1; i * prime[j] <= n; j++) {
            v[i * prime[j]] = true;
            if (i % prime[j] == 0) break;
        }
    }
    for (int k = 6; k <= n; k += 6) {
        int i = k + 1;
        if (!v[i]) prime[++tot] = i;
        for (int j = 1; i * prime[j] <= n; j++) {
            v[i * prime[j]] = true;
            if (i % prime[j] == 0) break;
        }
        i += 4;
        if (!v[i]) prime[++tot] = i;
        for (int j = 1; i * prime[j] <= n; j++) {
            v[i * prime[j]] = true;
            if (i % prime[j] == 0) break;
        }
    }
}

可以看到我们手动处理了 \([2,5]\) 的素数，然后使用了 \(6k \pm 1\) 的结论，直接六个六个筛，但是这么筛会在一定程度上漏筛很多 \(2^n3^m\) 形式的合数，但因为这些形式的合数都是 \(6\) 的倍数，在后面筛的循环中不受影响。

这个优化仅限于我们求取 \([1, n]\) 所有素数的情况，如果我们依赖于筛的其他副产物，如最小素因子，欧拉函数等，则该算法不正确。

实测中加了这个优化代码能快上 2 倍！

线性筛卡常技巧

Table of Contents

Table of Contents

素数的 \(6k \pm 1\) 判定方法

常数优化