欧拉筛（模板）

     {质数*质数  
合数={合数*质数  ==> 质数*质数*质数
     {合数*合数  ==> 质数*质数*质数*质数  ==>  质数*合数

==> 合数={质数*质数
         {质数*合数

欧拉筛：让每个合数被其最小质因子给筛掉      //由于每个数只被筛一次，时间复杂度为O(n)
#include<bits/stdc++.h>
using namespace std;
int const N=1e3+7;
int n,cnt;
int v[N];     //v[i]表示(数字)i的最小质因子
int prime[N];  //prime为质数表
int main(){
    cin >> n;
    for(int i=2;i<=n;++i){
        if(v[i]==0){     //若i的最小质因子为0，表示i是质数  //即没有被筛过，则记录素数
            v[i]=i;      //即i的最小质因子是自己
            prime[++cnt]=i;   //第cnt个素数是i
        }
        //两种for，它们意思一样，语句顺序不一样而已，以后用第一种
        //第一种
        for(int j=1;j<=cnt && prime[j]<=v[i] && i*prime[j]<=n;++j){    //访问之前所有的质数  //prime[j]<=v[i]是因为要用prime[j]作为最小质因子筛数
            //if( i*prime[j]>n ) break;
            v[ i*prime[j] ]=prime[j];  //i*prime[j]的最小质因子为prime[j]
        }
        //第二种
        /*for(int j=1;j<=cnt;++j){    //访问之前所有的质数
            if( v[i]<prime[j] || i*prime[j]>n ) break;  //若i的最小质因子即v[i]比prime[j]小，则 i*prime[j] 这个数之前就被v[i](i的最小质因子)给筛掉了
            v[ i*prime[j] ]=prime[j];
        }*/

    }
    for(int i=1;i<=cnt;++i){
      cout << prime[i] << endl;
    }
    return 0;
}