C++数组求n以内的所有素数

在C++中，求解一定范围内（比如n以内）的所有素数，可以使用埃拉托斯特尼筛法（Sieve of Eratosthenes）。这是一种经典算法，通过标记并删除合数来找到素数。下面是简单的步骤：

1. 创建一个布尔类型的数组`isPrime`，大小为`n+1`，默认所有元素初始化为true，因为开始认为从2到n的每一个数字都是素数。

2. 遍历从2开始，直到√n（向下取整），对于每个素数p：
- 如果`isPrime[p]`为true，则它是素数，将它的倍数（除了它自身）标记为非素数，即`isPrime[2*p..n] = false`。
- 因为只需要检查到√n，因为超过这个范围的因子都与较小的因子配对存在，例如4和6的因子分别是2和3。

3. 最后，遍历`isPrime`数组，找出所有值为true的位置，它们对应的索引就是n以内的素数。

#include <iostream>
#include <vector>
using namespace std;

void sieveOfEratosthenes(int n) {
    vector<bool> isPrime(n+1, true);
    isPrime[0] = isPrime[1] = false;
    for (int p=2; p*p<=n; ++p) {
        if (isPrime[p]) {
            for (int i=p*p; i<=n; i += p)
                isPrime[i] = false;
        }
    }

    // 输出素数
    for (int p=2; p<=n; ++p)
        if (isPrime[p])
            cout << p << " ";
}

int main() {
    int n = 50; // 想要查找的范围
    sieveOfEratosthenes(n);
    return 0;
}

运行上述代码，会打印出50以内的所有素数。