C++用筛法求N之内的素数。(1<=N<=10000000)（时间复杂度小,用一维数组，不用函数）

在C++中，可以使用埃拉托斯特尼筛法（Sieve of Eratosthenes）来找出小于等于给定数N的所有素数。这是一种非常高效的方法，它通过不断排除合数来筛选出素数，其时间复杂度大约是O(N log log N)，在一维数组中操作简单，不需要函数封装。

以下是简单的步骤：

1. 创建一个大小为N+1的一维布尔型数组isPrime，初始全部设为true，表示所有数字都是潜在的素数。
2. 从2开始，遍历到sqrt(N)（因为大于这个数的因子一定已经存在较小的值）。对于每个素数p：
a. 如果isPrime[p]仍然为true，说明它是有效的素数，更新isPrime数组，将p的倍数（除了p本身）都标记为false，因为它们不是素数。
i. 从p * p开始，每次加p，直到超过N。
3. 遍历结束后，isPrime[i]为true的那些数就是1到N之间的素数。

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

bool isPrime[10000001];

int main() {
    int N = 10000000;
    
    // 初始化所有的数为质数
    for (int i = 0; i <= N; ++i)
        isPrime[i] = true;

    // 筛选过程
    for (int p = 2; p * p <= N; ++p) { // 只需考虑p <= sqrt(N)
        if (isPrime[p]) { // p是素数
            for (int i = p * p; i <= N; i += p) { // 将p的倍数标记为非素数
                isPrime[i] = false;
            }
        }
    }

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

    return 0;
}