基本思想：对于不超过MAXN的每个素数i，删除2*i, 3*i…k*i(k*i<=MAXN)，当处理完所有数之后，剩下的就是素数了。
时间复杂度：
。
例子：
MAXN = 30:
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
----------------------------------
从第一个素数2开始：
2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
删除2的倍数（除本身外）后：
*2 3 5 7 9
11 13 15 17 19
21 23 25 27 29
下一个素数为3，删除3的倍数（同上）后。
*2 *3 5 7
11 13 17 19
23 25 29
重复上述操作。
最终筛出来的素数表如下：
2 3 5 7 11 13 17 19 23 29
代码：
const int MAXN=1000;
bool mark[MAXN];
void sieve_prime()
{
memset(mark,true,sizeof(mark));
mark[0]=mark[1]=false;
for (int i=2;i<=sqrt(MAXN);i++)
{
if (mark[i]){
for(int j=i*i;j<MAXN;j+=i)
mark[j]=false;
}
}
}
程序：
#include <cmath>
#include <vector>
#include <iostream>
using namespace std;
vector<int>primes;
void Sieve_Prime(int n){
for(int i=2;i<=n;++i){
int root = int(sqrt(i))+1;
bool found =false;
for(vector<int>::iterator it = primes.begin();it!=primes.end()&& *it<root; it++){
if(i % *it==0)
{found=true;break;}
}
if(!found)primes.push_back(i);
}
}
int main()
{
int n;
cin>>n;
Sieve_Prime(n);
for(vector<int>::iterator it =primes.begin(); it!=primes.end(); it++)
cout<<*it<<endl;
return 0;
}