埃氏筛做法

代码思路
埃氏筛预处理素数
用数组 p 标记 100 万内素数，memset 初始全为素数，再剔除 0、1 与所有合数，实现 O (1) 快速判素。
纯粹素数校验函数 f
先判断自身是素数；数字大于 9 时循环计算最高位权重，截取去掉最高位后的数，每一步都校验是否为素数，全部满足才返回真。
主程序遍历输出
先打素数表，读取 N；遍历 2~N，用 flag 控制空格格式，筛选并打印所有纯粹素数。
代码：

#include<bits/stdc++.h>
using namespace std;
// 存储1e6范围内素数标记
bool p[1000005];

// 埃氏筛打素数表
void s(){
    memset(p,1,sizeof(p)); // 初始全部标记为素数
    p[0]=p[1]=0; // 0、1不是素数
    for(int i=2;i*i<1000000;i++){
        if(p[i]){ // i是素数，筛除其所有倍数
            for(int j=i*i;j<1000000;j+=i){
                p[j]=0;
            }
        }
    }
}

// 判断x是否为纯粹素数
bool f(int x){
    if(!p[x]){ // 自身不是素数直接返回false
        return 0;
    }
    int t,d;
    while(x>9){ // 数字为多位数时循环截去最高位
        d=1;t=x;
        while(t/=10){ // 计算最高位的权重(10/100/1000...)
            d*=10;
        }
        x%=d; // 截去最高位，保留后面数字
        if(!p[x]){ // 截取后的数非素数，不符合条件
            return 0;
        }
    }
    return 1; // 每一步截取后都是素数，是纯粹素数
}
int n,flag=1;
int main(){
    s(); // 预处理素数表
    cin>>n;
    // 遍历2~n，筛选纯粹素数输出
    for(int i=2;i<=n;i++){
        if(f(i)){
            if(!flag){ // 非第一个数先输出空格分隔
                cout<<' ';
            }
            flag=0; // 标记已经输出过数字
            cout<<i;
        }
    }
    return 0;
}