Eratosthenes筛选法（C++版）

Sieve of Eratosthenes

使用埃拉托斯特尼筛选法计算小于100000的素数。

埃拉托斯特尼筛选法是最为知名的产生素数的筛选法，适用于产生最小的N个素数。

该方法的唯一缺点是使用的存储空间大，可以进一步改进。

另外，该算法也不适用于计算某个范围内的全部素数。

C++版使用的标志是布尔标志，比起C语言版（用整数数组作为标识太浪费空间；用位运算逻辑太复杂，易出错），使用的空间上改进相当多，并且逻辑也十分简单。

这是一个基础程序，用到的时候可以拷贝修改加以利用。

程序如下：

/*
 * 筛选法计算小于100000的素数
 * 筛选法求最小的素数序列，原本是不朽的数学家们手工计算的方法，
 */

#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;
}