埃拉托斯特尼筛法

算法原理
初始化：
创建一个布尔数组 isPrime，长度为 n+1，并将所有元素初始化为 true。
数组的索引表示数字，值表示该数字是否为素数。
标记非素数：
从2开始，逐步标记所有素数的倍数为 false。
对于每个素数 p，从 p2p^2 开始，以 p 为步长，将所有倍数标记为 false。
输出结果：
遍历数组，所有值为 true 的索引即为素数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<int> sieveOfEratosthenes(int n) {
    vector<bool> isPrime(n + 1, true); 
    vector<int> primes; // 用于存储素数

    isPrime[0] = isPrime[1] = false;

    for (int p = 2; p * p <= n; p++) {
        if (isPrime[p]) {
            // 标记p的所有倍数为false
            for (int i = p * p; i <= n; i += p) {
                isPrime[i] = false;
            }
        }
    }

    // 收集所有素数
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            primes.push_back(i);
        }
    }

    return primes;
}