筛选质数在C++中有多种方法，下面列出几种常见的方法并提供相应的代码示例：

1. 枚举法（试除法）

这是最简单的质数筛选方法，通过逐个检查每个数是否能被小于它的数整除来判断是否为质数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <cmath>

bool isPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) return false;
    }
    return true;
}

int main() {
    int n = 30;
    for (int i = 2; i <= n; i++) {
        if (isPrime(i)) {
            cout << i << " ";
        }
    }
    return 0;
}

2. 埃拉托斯特尼筛法（Sieve of Eratosthenes）

这种方法通过标记所有合数来筛选出质数。

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
#include <iostream>
#include <vector>

void SieveOfEratosthenes(int n) {
    vector<bool> prime(n + 1, true);
    // 遍历所有可能的素数 p
    for (int p = 2; p * p <= n; p++) {
        // 如果 p 是一个素数（即 prime[p] 为 true）
        if (prime[p]) {
            // 标记 p 的所有倍数为非素数 
            for (int i = p * p; i <= n; i += p) {
                prime[i] = false;
            }
        }
    }
    for (int p = 2; p <= n; p++) {
        if (prime[p]) {
            cout << p << " ";
        }
    }
}

int main() {
    int n = 30;
    SieveOfEratosthenes(n);
    return 0;
}

3. 线性筛法（Linear Sieve）

线性筛法避免了重复标记，通过每个数的最小质因子来筛选。

cpp

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
#include <iostream>
#include <vector>

void LinearSieve(int n) {
    vector<int> primes;
    vector<bool> isPrime(n + 1, true);
    for (int i = 2; i <= n; ++i) {
        if (isPrime[i]) {
            primes.push_back(i);
        }
        for (int j = 0; j < primes.size() && i * primes[j] <= n; ++j) {
            isPrime[i * primes[j]] = false;
            if (i % primes[j] == 0) break;
        }
    }
    for (int prime : primes) {
        cout << prime << " ";
    }
}

int main() {
    int n = 30;
    LinearSieve(n);
    return 0;
}

4. 奇数筛法

优化后的埃拉托斯特尼筛法，只筛选奇数。

cpp

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
#include <iostream>
#include <vector>

void OddSieve(int n) {
    if (n >= 2) cout << 2 << " ";
    vector<bool> isPrime((n + 1) / 2, true);
    for (int i = 3; i * i <= n; i += 2) {
        if (isPrime[i / 2]) {
            for (int j = i * i; j <= n; j += 2 * i) {
                isPrime[j / 2] = false;
            }
        }
    }
    for (int i = 1; 2 * i + 1 <= n; ++i) {
        if (isPrime[i]) {
            cout << 2 * i + 1 << " ";
        }
    }
}

int main() {
    int n = 30;
    OddSieve(n);
    return 0;
}

5. 欧拉筛法（Euler Sieve）

欧拉筛法是对埃拉托斯特尼筛法的优化，保证每个合数只被筛选一次。

cpp

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
#include <iostream>
#include <vector>

void EulerSieve(int n) {
    vector<int> primes;
    vector<bool> isPrime(n + 1, true);
    for (int i = 2; i <= n; ++i) {
        if (isPrime[i]) {
            primes.push_back(i);
        }
        for (int j = 0; j < primes.size() && i * primes[j] <= n; ++j) {
            isPrime[i * primes[j]] = false;
            if (i % primes[j] == 0) break;
        }
    }
    for (int prime : primes) {
        cout << prime << " ";
    }
}

int main() {
    int n = 30;
    EulerSieve(n);
    return 0;
}

这些方法各有优缺点，选择哪种方法取决于具体的应用场景和数据规模。