c++用Eratosthenes寻找素数

Eratosthenes筛法是一种古老而高效的算法，用于找出小于或等于给定数N的所有素数。该算法的基本思想是从未标记的数中选出最小的数作为素数，然后将这个数的所有倍数标记为非素数，接着在未标记的数中选出下一个最小的数重复此过程，直到达到某个上限为止。

在C++中使用Eratosthenes筛法寻找素数的基本步骤如下：

1. 创建一个布尔数组`prime[0..n]`，并将所有元素初始化为`true`。一个值在`prime[i]`为`true`表示数字`i`是素数，为`false`则表示不是素数。
2. 从最小的素数2开始，将所有2的倍数标记为非素数。
3. 找到下一个未标记的数（即下一个素数），并重复步骤2，将该素数的所有倍数标记为非素数。
4. 重复以上步骤直到达到或超过指定的上限N。

下面是一个简单的C++代码示例，展示了如何使用Eratosthenes筛法来找到所有小于或等于N的素数：

#include <iostream>
#include <vector>
#include <cmath>

void SieveOfEratosthenes(int n) {
    std::vector<bool> prime(n + 1, true);
    prime[0] = prime[1] = false;

    for (int p = 2; p * p <= n; p++) {
        if (prime[p] == true) {
            for (int i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }

    std::cout << "以下是小于或等于 " << n << " 的所有素数: \n";
    for (int p = 2; p <= n; p++)
        if (prime[p])
            std::cout << p << " ";
}

int main() {
    int n = 30; // 可以更改这个值来寻找小于或等于任何数的素数
    SieveOfEratosthenes(n);
    return 0;
}

运行这段代码将会输出小于或等于30的所有素数。