素数筛

素数筛

核心概念

埃氏筛（Eratosthenes）：从小到大枚举每个素数，将其倍数标记为合数。时间复杂度 $O(n\log \log n)$。

优化：只需筛到 $\sqrt{n}$，可从 $i^2$ 开始标记。

欧拉筛（线性筛）：每个合数只被其最小质因子标记一次，时间复杂度 $O(n)$。

代码实现

// 埃氏筛
vector<int> prime;
bool is_prime[N];
void Eratosthenes(int n) {
  fill(is_prime, is_prime + n + 1, true);
  is_prime[0] = is_prime[1] = false;
  for (int i = 2; i * i <= n; ++i)
    if (is_prime[i])
      for (int j = i * i; j <= n; j += i)
        is_prime[j] = false;
  for (int i = 2; i <= n; ++i)
    if (is_prime[i]) prime.push_back(i);
}
 
// 欧拉筛（线性筛）
vector<int> pri;
bool not_prime[N];
void pre(int n) {
  for (int i = 2; i <= n; ++i) {
    if (!not_prime[i]) pri.push_back(i);
    for (int pri_j : pri) {
      if (i * pri_j > n) break;
      not_prime[i * pri_j] = true;
      if (i % pri_j == 0) break;
    }
  }
}

区间筛

求 $[L,R]$ 内的素数（$R-L\le 10^6$，$R\le 2^{31}$）：用 $[2,\sqrt{R}]$ 的素数筛区间 $[L,R]$。

练习题目

题目	描述
P3383 【模板】线性筛素数	线性筛求 $n$ 以内素数
P1835 素数密度	区间筛
LeetCode 204 计数质数	埃氏筛计数

相关链接

• 快速幂与模运算
• GCD与EXGCD
• 中国剩余定理
• 路径D-DSA算法刷题

来源：OI-wiki sieve.md

多平台练习

| 洛谷 | 本题单 | 竞赛基础 |
| POJ (北大) | PKU JudgeOnline | 经典题目，适合巩固 |
| HDU (杭电) | HDU OJ | 暑期多校训练 |
| Codeforces | Codeforces | 国际竞赛，适合提升 |