质数筛选算法详解#

1
// 暴力法：O(n√n)
2
bool isPrime(int x) {
3
    if (x < 2) return false;
4
    for (int i = 2; i * i <= x; i++) {
5
        if (x % i == 0) return false;
6
    }
7
    return true;
8
}
9

10
// 筛选 1 到 n 的所有质数
11
for (int i = 1; i <= n; i++) {
12
    if (isPrime(i)) {
13
        // i 是质数
14
    }
15
}

1
初始: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
2
标记2的倍数: 2 3 X 5 X 7 X 9 X  11 X  13 X  15 X  17 X  19 X  21 X  23 X  25 X  27 X  29 X
3
标记3的倍数: 2 3 X 5 X 7 X X X  11 X  13 X  X  X  17 X  19 X  X  X  23 X  25 X  X  X  29 X
4
标记5的倍数: 2 3 X 5 X 7 X X X  11 X  13 X  X  X  17 X  19 X  X  X  23 X  X  X  X  X  29 X
5
...
6
最终质数: 2 3 5 7 11 13 17 19 23 29

1
#include <iostream>
2
using namespace std;
3

4
const int MAXN = 10000000;  // 一千万
5
bool isPrime[MAXN + 1];
6

7
void sieve() {
8
    // 1. 初始化：假设所有数都是质数
9
    for (int i = 2; i <= MAXN; i++) {
10
        isPrime[i] = true;
11
    }
12

13
    // 2. 埃氏筛：标记合数
14
    for (int i = 2; i * i <= MAXN; i++) {
15
        if (isPrime[i]) {
16
            // 标记 i 的所有倍数为合数
17
            // 优化：从 i² 开始，因为 i×2, i×3, ..., i×(i-1)
18
            // 已经被更小的质数标记过了
19
            for (int j = i * i; j <= MAXN; j += i) {
20
                isPrime[j] = false;
21
            }
22
        }
23
    }
24
}
25

26
int main() {
27
    sieve();
28

29
    // 使用示例：查询质数
30
    cout << "10 以内的质数: ";
31
    for (int i = 2; i <= 10; i++) {
32
        if (isPrime[i]) {
33
            cout << i << " ";
34
        }
35
    }
36
    // 输出: 2 3 5 7
37

38
    return 0;
39
}

1
#include <iostream>
2
#include <vector>
3
using namespace std;
4

5
const int MAXN = 10000000;
6
bool isPrime[MAXN + 1];
7
vector<int> primes;  // 存储所有质数
8

9
void eulerSieve() {
10
    // 1. 初始化
11
    for (int i = 0; i <= MAXN; i++) {
12
        isPrime[i] = true;
13
    }
14
    isPrime[0] = isPrime[1] = false;
15

16
    // 2. 欧拉筛
17
    for (int i = 2; i <= MAXN; i++) {
18
        if (isPrime[i]) {
19
            primes.push_back(i);  // 记录质数
20
        }
21

22
        // 用已知质数标记合数
23
        for (int j = 0; j < primes.size() && primes[j] * i <= MAXN; j++) {
24
            isPrime[primes[j] * i] = false;
25

26
            // 关键优化：避免重复标记
27
            if (i % primes[j] == 0) break;
28
        }
29
    }
30
}
31

32
int main() {
33
    eulerSieve();
34

35
    cout << "前 10 个质数: ";
36
    for (int i = 0; i < 10; i++) {
37
        cout << primes[i] << " ";
38
    }
39
    // 输出: 2 3 5 7 11 13 17 19 23 29
40

41
    return 0;
42
}

1
j = 0: primes[0] = 2
2
  标记 6×2 = 12 (12 的最小质因子是 2) ✅
3
  6 % 2 == 0, break! ⛔
4

5
// 如果不 break，会继续：
6
j = 1: primes[1] = 3
7
  标记 6×3 = 18 (但 18 的最小质因子是 2，不是 3) ❌
8
  这会导致重复标记！

1
// 测试 n = 10^7 的运行时间
2
埃氏筛: 约 0.15 秒
3
欧拉筛: 约 0.10 秒
4

5
// 测试 n = 10^8 的运行时间
6
埃氏筛: 约 1.5 秒
7
欧拉筛: 约 1.0 秒

1
int countPrimes(int n) {
2
    sieve();
3
    int count = 0;
4
    for (int i = 2; i <= n; i++) {
5
        if (isPrime[i]) count++;
6
    }
7
    return count;
8
}

1
int kthPrime(int k) {
2
    eulerSieve();  // 使用欧拉筛，因为需要质数表
3
    return primes[k - 1];
4
}

1
vector<int> primesInRange(int L, int R) {
2
    sieve();
3
    vector<int> result;
4
    for (int i = max(2, L); i <= R; i++) {
5
        if (isPrime[i]) {
6
            result.push_back(i);
7
        }
8
    }
9
    return result;
10
}

1
// 错误
2
const int MAXN = 1000000;
3
bool isPrime[MAXN];
4
for (int i = 2; i <= MAXN; i++)  // 越界！
5

6
// 正确
7
const int MAXN = 1000000;
8
bool isPrime[MAXN + 1];  // 或者改为 i < MAXN

1
// 0 和 1 不是质数
2
isPrime[0] = isPrime[1] = false;

1
// 低效
2
for (int j = i * 2; j <= MAXN; j += i)
3

4
// 高效
5
for (int j = i * i; j <= MAXN; j += i)

1
// 例如：筛选 [10^12, 10^12 + 10^6] 的质数
2
// 先筛 [1, √R] 的质数，再用它们标记 [L, R]

1
#include <bitset>
2
bitset<MAXN> isPrime;  // 比 bool 数组省 8 倍空间