跳转至

筛法及其应用

质数筛法

问题一

求 \(1 \sim n\) 中所有的质数.

暴力筛法

#include <iostream>
const int N = 10000100;
bool st[N];
int n, primes[N], cnt = 0;

int main() {
  cin >> n;
  for (int i = 2; i <= n; i++) {
    if (!st[i]) primes[cnt++] = i;
    for (int j = i + i; j <= n; j += i) st[i] = true;
  }
  for (int k = 0; k < cnt; k++) cout << primes[k] << " ";
  cout << endl;
  return 0;
}

  • 从 \(2\) 到 \(n\) 枚举变量 \(i\), 如果当前 \(i\) 未被 \(2 \sim i\) 筛掉说明 \(i\) 为质数.

  • 对于每次枚举变量 \(i\), 将 \(i\) 的所有倍数筛掉.

时间复杂度为

\[ \begin{equation} \begin{aligned} O(n) &= \quad \frac{n}{2} + \frac{n}{3} + \frac{n}{4} + \ldots + \frac{n}{n} \\ \\ & = n\ (\frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \ldots + \frac{1}{n}) \\ \\ & = n\ (log_e^{n} + \gamma) \quad (调和级数的前 \ n \ 项和) \end{aligned} \end{equation} \]

埃拉托斯特尼筛法

暴力筛法会有很多数被重复筛掉, 性能较低.

考虑到如果一个数字是合数, 那么这个合数及其所有的倍数肯定已经被 \(2 \sim n\) 中的某些质数筛掉, 不必重复筛除, 所以当变量 \(i\) 为合数时, 可以忽略不考虑.

#include <iostream>
const int N = 10000100;
bool st[N];
int n, primes[N], cnt = 0;

int main() {
  cin >> n;
  for (int i = 2; i <= n; i++) {
    if (!st[i]) {
    primes[cnt++] = i;
    //------------------------------------------------
    for (int j = i + i; j <= n; j += i) st[i] = true;
    //------------------------------------------------
    // 埃氏筛法: 当 i 为质数时筛掉其倍数, 当 i 为合数时不考虑
    }
  }
  for (int k = 0; k < cnt; k++) cout << primes[k] << " ";
  cout << endl;
  return 0;
}

时间复杂度为

\[ O \left(n \sum^{\pi(n)}_{k=1}\frac{1}{p_k}\right) = O\ (n\ log\ log\ n) \]

线性筛法

由于埃氏筛法仍然存在 一个合数被多个质数重复筛掉 的情况, 可进一步优化.

#include <iostream>
const int N = 10000100;
bool st[N];
int n, primes[N], cnt = 0;

int main() {
  cin >> n;
  for (int i = 2; i <= n; i++) {
    if (!st[i]) primes[cnt++] = i;
    //---------------------------------------------
    for (int j = 0; primes[j] <= n / i; j++) {
      st[primes[j] * i] = true;    
      if (i % primes[j] == 0) break;
    }
    //---------------------------------------------
  }
  for (int k = 0; k < cnt; k++) cout << primes[k] << " ";
  cout << endl;
  return 0;
}
线性筛法的正确性

  • 对于任意合数, 只会被其最小的质因数筛掉, 由于其最小质因数唯一, 所以只会被筛一次.
  • 对于任意合数 \(x\), 必定会在当 \(i\) 枚举到 \(\frac{x}{primes[j]}\) 时被筛掉.

由于每个合数只会被筛一次,所以线性筛法的时间复杂度为 \(O(n)\).

最后更新: 2021-11-26
Back to top