数组-筛法求素数

好的，我可以为您解答关于数组-筛法求素数的问题。

筛法求素数，也称为埃氏筛法，是一种非常高效的求解素数的方法。

其基本思想是：先用一个数组来表示从2到N的所有自然数，假设这个数组为prime[N+1]，初始时，将prime[2]~prime[N]赋值为1，表示这些数都是素数。

然后从2开始，依次将2的倍数、3的倍数、4的倍数……以此类推，都标记为合数。具体实现时，可以使用两个循环嵌套，外层循环枚举2~N之间的所有自然数，内层循环枚举当前数的所有倍数，将它们标记为合数，即将prime[i]的倍数prime[i*j]置为0。

最后，所有值为1的prime[i]都是素数。

下面是一个简单的C++代码实现：

const int N = 1000000;
int prime[N+1]; // 用来存储素数的数组

void sieve(int n) {
    memset(prime, 1, sizeof(prime)); // 初始化为1，表示都是素数
    prime[0] = prime[1] = 0; // 0和1不是素数
    for(int i=2; i<=n; i++) {
        if(prime[i]) { // 如果是素数
            for(int j=2; i*j<=n; j++) {
                prime[i*j] = 0; // 将i的倍数标记为合数
            }
        }
    }
}

这个算法的时间复杂度为O(NloglogN)，非常适用于N比较大的情况。