跳转至

素数筛法

Luogu P3383 线性筛素数

给定一个范围n，有q个询问，每次输出第k小的素数

需要在线性时间范围内

埃氏筛法

从小到大枚举每个数，

如果当前数没划掉，必定是质数，记录该质数

枚举当前质数的倍数，必定是合数 划掉合数

// j 从 i * i 开始枚举
vector<int> vis(n); // 为合数
vector<int> prim(n); // 记录质数
int cnt = 0; // 质数个数

void Eratosthenes(int n) {
  for (i64 i = 2; i < n; i ++) {
    if (!vis[i]) {
      prim[cnt++] = i;
      for (i64 j = i * i; j <= n; j += i) vis[j] = 1;
    }
  }
}
时间复杂度: \(O(n \log \log n)\)

线性筛法（欧拉筛）

从小到大枚举每个数

  1. 如果当前数没划掉，必定是质数，记录该质数

  2. 枚举已记录的质数（如果合数已越界则中断）

    1. 合数未越界，则划掉合数

    2. 条件 i%p == 0，保证合数只被最小质因子划掉

      • 若 i 是质数，则最多枚举到自身中断

      • 若 i 是合数，则最多枚举到自身的最小质数中断

vector<int> vis(n);
vector<int> prim(n);
int cnt = 0;

void get_prim(int n) {
  for (int i = 0; i <= n; i ++) {
    if (!vis[i]) prim[cnt ++] = i;
    for (int j = 1; 1ll * i * prim[j] <= n; j ++) {
      vis[i * prim[j]] = 1;
      if (i % prim[j] == 0) break;
    }
  }
}