质数筛

线性筛

线性筛可以求解积性函数等具有一些特殊性质的函数。核心思路在于，我们对于每个数 $q$ 去枚举 $pq$，其中 $p$ 是小于 $q$ 的质数。一般需要讨论三种情况：

1. $q$ 是一个新发现的质数；
2. $p\mid q$，说明 $p$ 是 $q$ 的质因子；
3. $p\nmid q\iff p\perp q$。

下面是几个例子。

欧拉函数

定义： $\phi (n)$ 表示不超过 $n$ 的正整数中，与 $n$ 互质的个数。

性质：

1. 对于互质的两个数是积性函数：若 $(a,b)=1$ 则 $\phi (ab)=\phi (a)\phi (b)$
2. 如果 $p$ 是质数，则有 $\phi (p^m)=(p-1)p^{m-1}$

在线性筛的基础上求出 $\phi (xi)$ ，其中 $i$ 是质数：

1. 如果 $i\mid x$ 则 $x$ 有 $xi$ 的所有因子，所以

   $$\begin{array}{rl}\phi (xi)& =\phi (p_1^{m_1}\cdots p_s^{m_s})\\ & =\prod _i(p_i-1)p_i^{m_i-1}\\ & =\prod _i{p}_i^{m_i}\prod _i\left(1-\frac{1}{p_i}\right)\\ & =ix\prod _i\left(1-\frac{1}{p_i}\right)\\ & =i\phi (x).\end{array}$$

2. 否则，由于 $x$ 和 $i$ 互质，所以

   $$\phi (xi)=\phi (x)\phi (i)=(i-1)\phi (x).$$

想到这个分类讨论是来源于想用积性函数的性质，但是不一定互质，进一步想到不互质就一定是 $i\mid x$ 。

vector<int> get_phi(int n) {
    vector<bool> not_prime(n + 1);
    vector<int> res;
    vector<int> phi(n + 1);
    phi[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (not not_prime[i]) {
            res.emplace_back(i);
            phi[i] = i - 1;
        }
        for (auto&& x : res) {
            if (i * x > n) break;
            not_prime[i * x] = 1;
            if (i % x == 0) {
                // phi(n) = n * prod((p - 1) / p)
                // => phi(i * x) = i * x * prod((p - 1) / p) = (i * prod((p - 1) / p)) * x = phi(i) * x,
                // since `i` covers all factors of i * x
                phi[i * x] = phi[i] * x;
                break;
            } else {
                // i coprimes x
                // phi(i * x) = phi(i) * phi(x) = phi(i) * (x - 1)
                phi[i * x] = phi[i] * (x - 1);
            }
        }
    }
    return phi;
}

因数个数

设 $num(n)$ 表示 $n$ 的最小质因子出现的次数，$f(n)$ 表示 $n$ 的因数个数。

1. 当 $q$ 为质数时，$f(q)=2$；
2. 当 $p\mid q$ 时，根据线性筛的性质可知 $p$ 是 $pq$ 的最小质因子，所以我们更新 $num(pq)$ 的值，并用它重新计算 $f(pq)$；
3. 当 $p\nmid q$ 时，$num(pq)=1$，因为此时 $pq$ 的最小质因子 $p$ 不在 $q$ 中出现。

pair<vector<int>, vector<int>> factcount(int n) {
    vector<bool> not_prime(n + 1);
    vector<int> res(n + 1), num(n + 1);
    vector<int> primes;
    res[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (not not_prime[i]) {
            res[i] = 2;
            num[i] = 1;
            primes.emplace_back(i);
        }
        for (auto&& x : primes) {
            if (i * x > n) break;
            not_prime[i * x] = 1;
            if (i % x == 0) {
                num[i * x] = num[i] + 1;
                res[i * x] = res[i] / num[i * x] * (num[i * x] + 1);
                break;
            }
            num[i * x] = 1;
            res[i * x] = res[i] * 2;
        }
    }
    return {primes, res};
}

质因数个数

仍然讨论三种情况。设 $f(n)$ 表示 $n$ 的质因子个数，则有

1. 当 $q$ 是质数时，$f(q)=1$；
2. 当 $p\mid q$ 时，显然 $p$ 已经被 $q$ 考虑过了，所以 $f(pq)=f(q)$；
3. 当 $p\nmid q$ 时，有 $p\perp q$，所以 $f(pq)=f(q)+1$。

TIP

这个问题也可以通过求出所有的质数、再枚举这些质数的倍数来求解，并且由于质数的个数是 $O\left(\frac{n}{\log n}\right)$ 所以复杂度同样是线性的。然而，实际经验表明这样做的常数会非常大，不如用线性筛直接求解。

vector<int> primecount(int n) {
    vector<bool> not_prime(n + 1);
    vector<int> primes;
    vector<int> res(n + 1);
    for (int i = 2; i <= n; ++i) {
        if (not not_prime[i]) {
            primes.emplace_back(i);
            res[i] = 1;
        }
        for (auto&& x : primes) {
            if (i * x > n) break;
            not_prime[i * x] = 1;
            if (i % x == 0) {
                res[i * x] = res[i];
                break;
            }
            res[i * x] = res[i] + 1;
        }
    }
    return res;
}

最小质因数

vector<int> soe(int n) {
    vector<bool> not_prime(n + 1);
    vector<int> res;
    vector<int> minp(n + 1);
    minp[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (not not_prime[i]) {
            res.emplace_back(i);
            minp[i] = i;
        }
        for (auto&& x : res) {
            if (ll(1) * i * x > n) break;
            not_prime[i * x] = 1;
            minp[i * x] = x;
            if (i % x == 0) break;
        }
    }
    return minp;
}

埃筛

埃筛虽然时间复杂度有 $O(n\log \log n)$，但是它可以只占用 is_prime 这个布尔数组的空间，用 bitset 还能进一步压缩。有的题目卡空间就是想让你用埃筛。

// @source https://oi-wiki.org/math/number-theory/sieve
vector<int> prime;
bool is_prime[N];
 
void Eratosthenes(int n) {
  is_prime[0] = is_prime[1] = false;
  for (int i = 2; i <= n; ++i) is_prime[i] = true;
  for (int i = 2; i <= n; ++i) {
    if (is_prime[i]) {
      prime.push_back(i);
      if ((long long)i * i > n) continue;
      for (int j = i * i; j <= n; j += i)
        is_prime[j] = false;
    }
  }
}