埃拉托斯特尼筛法c++

埃拉托斯特尼筛法是一种用于求解素数的算法，其基本思想是从2开始，将每个质数的倍数都标记成合数，以达到筛选素数的目的。以下是C++实现的代码：

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

const int MAXN = 100000;
bool sieveflag[MAXN+1] = {false, false, true};

void esieve(bool sflag[], int n) {
    // 初始化
    for(int i=3; i<=n; i++) {
        sflag[i++] = true;
        sflag[i] = false;
    }
    // 筛选
    int max = sqrt(n);
    for(int i=3; i<=max; i++){
        if(sflag[i]) {
            for(int j=i+i; j <= n; j+=i) sflag[j] = false;
        }
    }
}

int main() {
    esieve(sieveflag, MAXN);
    for(int i=2, num=0; i<=MAXN; i++){
        if(sieveflag[i]){
            ++num;
            cout << num << ":" << i <<endl;
        }
    }
    return 0;
}

该代码使用了布尔标志来标记素数，相比于使用整数数组作为标识，空间上有很大的改进。同时，该算法也比较简单易懂，适用于产生最小的N个素数。但是，该算法不适用于计算某个范围内的全部素数。