素数筛法听起来很高大上的算法，实际上算法思想却十分简单：对前面取得的素数，依次"去掉"取出的这个素数后面的所有该素数的倍数。最后剩下的素数表里面的就是要求的素数，效率很高。

#include<iostream>

using namespace std;

const int MAX_N=100000000;

int prime[MAX_N];//素数表

bool is_prime[MAX_N+1];

//返回n以内的素数的个数

int sieve(int n)

{

    int p=0;

    for(int i=0;i<=n;i++)is_prime[i]=true;

    is_prime[0]=is_prime[1]=false;

    for(int i=2;i<=n;i++)

    {

        if(is_prime[i])

        {

            prime[p++]=i;//素数打表

            for(int j=2*i;j<=n;j+=i)is_prime[j]=false;//去掉已有素数的倍数

        }

    }

    return p;

}

int main()

{

    int N;

    cout<<"求2到多少以内的素数个数?"<<endl;

    cin>>N;

    cout<<"2到"<<N<<"共有"<<sieve(N)<<"个素数"<<endl;

    return 0;

}

//或者让我们直接输出n以内的所有素数看一看：

#include<iostream>

#include<iomanip>

using namespace std;

const int MAX_N=100000000;

int prime[MAX_N];

bool is_prime[MAX_N+1];

//返回以内的素数的个数

int sieve(int n)

{

    int p=0;

    for(int i=0;i<=n;i++)is_prime[i]=true;

    is_prime[0]=is_prime[1]=false;

    for(int i=2;i<=n;i++)

    {

        if(is_prime[i])

        {

            prime[p++]=i;//素数打表

            for(int j=2*i;j<=n;j+=i)is_prime[j]=false;//去掉已有素数的倍数

        }

    }

    return p;

}

int main()

{

    int N;

    cout<<"求2到多少以内的素数?"<<endl;

    cin>>N;

    sieve(N);

    int cnt=0;

    for(int i=0;i<=N;i++)

    {

        if(is_prime[i])

        {cout<<setw(9)<<i;cnt++;if(cnt%8==0)cout<<endl;}

    }

    return 0;

}

甚至求解10万以内也很快：