에라토스테네스의 체(비트마스크)

#include <bits/stdc++.h>
#define l long long
#define INF 2e9
#define p pair<int,int>
#define vc vector<unsigned char>
#define F first
#define S second
using namespace std;

//unsigned char는 1바이트로 총 8비트의 공간이 있다.

bool isPrime(int k,vc &arr){
    return arr[k >> 3] & (1 << (k & 7));
}

void Set(int k,vc &arr){
    arr[k >> 3] &= ~(1 << (k & 7));
}

int main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

    int n,a,ans = 0;

    cin >> n;

    vc arr((1000+7) / 8 +1,255);

    Set(1,arr);

    for(int i=2;i*i<=1000;i++){
        if(isPrime(i,arr)){
            for(int j=i*i;j<=1000;j+=i)
                Set(j,arr);
        }
    }


    for(int i=0;i<n;i++){
        cin >> a;
        if(isPrime(a,arr)) cout << a << " ";
    }
}