素数筛模板

#include<bits/stdc++.h>
using namespace std;
#define MAXN 1000000
int c=0;//记录素数数组内素数个数
int prime[MAXN];//保存素数的数组
bool vis[MAXN];//判断某个数是否已经被访问
void euler(int n) {
  for(int i = 2; i <= n; ++i) { //老规矩，遍历区间
    if(vis[i] == false) //如果这个数未被访问，则是素数
      prime[++c] = i;     //将素数保存在素数数组里面，计数+1
    //下面for循环及里面的语句才是这个算法的精髓
    for(int j = 1; j <= c && i * prime[j] <= n; ++j) {
      vis[i * prime[j]] = true;
      if (i % prime[j] == 0)//这句话最重要，精髓！！！ 
        break;
    }
  }
}
int main() {
  euler(MAXN);
  for(int i=1;i<=100;i++){
    cout<<prime[i]<<endl;
  } 
}