埃筛：

#include <iostream>
#include <cstring>
#include <bitset>

const int N = 1e8 + 5;

int prime[N];
std::bitset <N> isPrime;

int main(){
    
    std::cin.tie(0)->sync_with_stdio(0);
    
    int n,q,cnt = 0;
    
    std::cin >> n >> q;
    isPrime.set();
    isPrime[0] = isPrime[1] = false;
    for (int i = 2;i * i <= n;i++)
        if (isPrime[i])
            for (int j = i * i;j <= n;j += i) 
                isPrime[j] = false;
    for (int i = 2;i <= n;i++)
        if (isPrime[i])
            prime[++cnt] = i;
    while (q--){
        
        int k;
        
        std::cin >> k;
        std::cout << prime[k] << '\n';
        
    }
    
    return 0;
}

记录 欧筛：

#include <iostream>
#include <cstring>
#include <bitset>

const int N = 1e8 + 5;

int prime[N];
std::bitset <N> isPrime;

int main(){
    
    std::cin.tie(0)->sync_with_stdio(0);
    
    int n,q,cnt = 0;
    
    std::cin >> n >> q;
    isPrime.set();
    isPrime[0] = isPrime[1] = false;
    for (int i = 2;i <= n;i++){
        
        if (isPrime[i]) prime[++cnt] = i;
        for (int j = 1;j <= cnt && i * prime[j] <= n;j++){
            
            isPrime[i * prime[j]] = false;
            if (i % prime[j] == 0) break;
            
        }
        
    }
    while (q--){
        
        int k;
        
        std::cin >> k;
        std::cout << prime[k] << '\n';
        
    }
    
    return 0;
}

记录