#include<bits/stdc++.h>//总思想，是一个数字一个数字*递进*进行筛去
using namespace std;
const int N=1000010;
int  prime[N];
int cnt;
bool st[N];
void get_prime(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i])//如果这个数字未被筛掉,那么作为质数存入
       {
           prime[cnt]=i;
           cnt++;
       }
       for(int j=2*i;j<=n;j+=i){
           st[j]=true;//将当前已经筛过的i的倍数全部标记为筛去 再递进到下一个数，下一个数也是同理，无论是否被存入数组，都应筛去其倍数//详见其原理
       }
       
    }
}


int main()
{
    int n;
    cin>>n;
    get_prime(n);
   for(int i=0;i<cnt;i++){
       cout<<prime[i]<<endl;
   }
}

优化

#include<bits/stdc++.h>//总思想，是一个数字一个数字*递进*进行筛去
using namespace std;
const int N=1000010;
int  prime[N];
int cnt;
bool st[N];
void get_prime(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i])//如果这个数字未被筛掉,那么作为质数存入
       {
           prime[cnt]=i;
           cnt++;   
 for(int j=2*i;j<=n;j+=i){           st[j]=true;//将所有素数的倍数删去即可，无需遍历2~p-1所有数   }
       }
   
       
    }
}


int main()
{
    int n;
    cin>>n;
    get_prime(n);
   for(int i=0;i<cnt;i++){
       cout<<prime[i]<<endl;
   }
}