线性筛素数

#include <iostream>
#include <bitset>
typedef long long ll;
const int sz=1e8+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; // *10
        }
        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 n=sscio::pull(); //n为查询范围,因为已经筛了超出题目范围素数了,所以无需处理
    int p=sscio::pull(); //查询的个数
    while(p--) {
        int k=sscio::pull(); //表示查询第 k 小的素数
        printf("%d\n", primes[k-1]); //因为我们下标从零开始 所以是k - 1
    }
}

signed main() {
    solve();
    return 0 ^ 0;
}

#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; // *10
        }
        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 n=sscio::pull(); //n为查询范围,因为已经筛了超出题目范围素数了,所以无需处理
    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;
}