线性筛卡常技巧

Posted on Views:

啊？卡常，没有啊？标程只是加了个小优化啊？

于是某人的欧拉筛就在n = 10^8的情况下被卡常死于非命。

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

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

  1. r = 0：显然有6 | n，n为合数。
  2. r = 1：n = 6k + 1可能是素数。
  3. r = 2：6k + 2 = 2(3k + 1)，在k \ge 1时n为合数。
  4. r = 3：6k + 3 = 3(2k + 1)，在k \ge 1时n为合数。
  5. r = 4：6k + 4 = 2(3k + 2)，n为合数。
  6. 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倍！