1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
| #include <iostream> #include <bitset> typedef long long ll; const int sz=1e5+10;
namespace sscio { inline ll pull() { ll sign = 1LL,res = 0LL; char ch = getchar(); for (;!isdigit(ch);ch=getchar()) { if (ch == '-') { sign *= -1LL; } } for (;isdigit(ch);ch = getchar()) { res = (res << 3) + (res << 1) - '0' + ch; } return sign * res; } }
using std::bitset; bitset<sz> primeTable; int primes[sz],prpp=0; void fetchPrimes(const int &ed) { primeTable.reset(); primeTable.set(0); primeTable.set(1); for(register int cx=2;cx<ed;cx++) { if(!primeTable[cx]) { primes[prpp++]=cx; } for (register int cy=0;cy<prpp&&cx*primes[cy]<ed;cy++) { primeTable.set(cx*primes[cy]); if (cx%primes[cy]==0) { break; } } } }
void solve() { fetchPrimes(sz-6); int p=sscio::pull(); int cnt = 0; while(p--) { int k=sscio::pull(); if (!primeTable[k]) { if (cnt==0) { cnt++; } else { putchar(' '); } printf("%d", k); } } }
signed main() { solve(); return 0 ^ 0; }
|