A80450.质数筛 题解

#include<bits/stdc++.h>
using namespace std;

const int N = 1e8+5;
bool a[N];
int p[6000000];
int cnt = 0;
int main(){
    a[1] = 1;
    for(int i = 2;i<=N;i++){
        if(a[i] == 0) p[++cnt] = i;
        for(int j = 1;j<=cnt&&p[j]*i<=N;j++){
            a[p[j]*i] = 1;
            if(i%p[j]==0) break;//关键
        }
    }
    ///\
    // | 欧拉筛
    //————————————————————————————————————————————————————————————
    // | 普通
    //\/
    int n,b[1000005],num,al = 0;
    cin>>n;
    for(int i = 0;i<n;i++){
        cin>>num;
        if(a[num]==0) b[al] = num,al++;
    }
    sort(b,b+al);
    for(int i = 0;i<al;i++){
        cout<<b[i]<<" ";
    }
    return 0;
}