#include<iostream>
#include<cmath>
using namespace std;
bool isprime(int x){//定义判断函数isprime，返回值类型为bool 
    if(x<=1)return false;//如果这个数≤1，那么它肯定不是素数，返回false 
    if(x==2)return true;//如果这个数=2，也需要特判，2是素数，返回true  
    for(int i=2;i<=x-1;i++){//枚举2到x-1 
        if(x%i==0)return false;
        /*如果这其中x能被任意一个i整除，说明x有除了1和它本身之外的其他因数，
        所以它不是素数，返回false*/
    }
    return true;//如果这个数不能被除了1和它本身之外的其他数整除，那么他就是素数，返回true 
} 
int main(){
    int n;//定义一个n，表示要输出的是1-n之间的素数 
    cin>>n;//输入表示范围的n 
    for(int i=1;i<=n;i++) {//枚举1-n之间的每一个数 
        if(isprime(i))cout<<i<<' ';//调用isprime函数，判断i是否为素数，如果返回true则输出 
    }
    return 0;//结束程序 
}

#include<iostream>
#include<cmath>
using namespace std;
bool isprime(int x){ 
    if(x<=1)return false; 
    if(x==2)return true; 
    for(int i=2;i*i<=x;i++){//等于int y=sqrt(x);for(int i=1;i<=y;i++)这种形式只是减少了函数的调用,实际的复杂度还是相同的
        if(x%i==0)return false;    
    }
    return true;
} 
int main(){
    int n; 
    cin>>n; 
    for(int i=1;i<=n;i++) { 
        if(isprime(i))cout<<i<<' '; 
    }
    return 0; 
}

#include<iostream>
#include<cmath>
using namespace std;
bool isprime[1005];//标记是否为素数，如果i为素数，则isprime[i]为0；否则为1
int n;//定义一个范围，表示从1-n 
void Aiprime(int x){
    isprime[1]=1;//1不是素数
    for(int i=2;i<=x;i++){
        if(isprime[i]==0){//如果i是素数，开始筛除i的倍数 
            for(int j=i*2;j<=x;j+=i)
            //从i的2倍（防止i被筛除）开始筛除合数，直到i比x大时停止，每次增加一倍 
                 isprime[j]=1; //筛去所有i的倍数
        }
    }
} 
int main(){
    cin>>n;
    Aiprime(n);//调用埃氏筛选出从1-n的所有素数 
    for(int i=1;i<=n;i++)//从1枚举到n 
        if(isprime[i]==0)cout<<i<<' ';//如果isprime[i]为0,说明i为素数，输出 
    return 0;
} 

#include<iostream>
#include<cmath>
using namespace std;
bool isprime[50005];//标记是否为素数，如果i为素数，则isprime[i]为0；否则为1
int prime[50005];//用来存素数
int cnt;//素数的个数 
int n;//定义一个范围，表示从1-n 
void Qprime(int x){
    isprime[1]=1;//1不是素数 
    for(int i=2;i<=x;i++){
        if(isprime[i]==0)prime[++cnt]=i;
        //如果i是素数，素数个数+1，把i存在prime数组的相应位置中
        for(int j=1;j<=cnt&&i*prime[j]<=x;j++){
            isprime[i*prime[j]]=1;//将i的素数倍标记为合数 
            if(i%prime[j]==0)break;
            //如果i能被素数prime[j]整除，那i*prime[j+1]这个合数一定也能被prime[j]整除，终止循环 
            //保证了一个合数只能被筛除一次，可以保证线性的时间复杂度
        } 
    }
} 
int main(){
    cin>>n;
    Qprime(n);//调用线性筛选出从1-n的所有素数 
    for(int i=1;i<=cnt;i++)cout<<prime[i]<<' ';
    //从1枚举到素数的个数cnt，输出prime数组里的所有素数 
    return 0;
}