Background

This problem has been updated: it now asks for querying the $k$-th smallest prime instead of primality testing.

Hint: The input/output and computation workload can be large.

• For C++: if you use cin for I/O, consider std::ios::sync_with_stdio(0) for acceleration, and use '\n' for newlines.
• For Java: using a linear sieve with optimized I/O can pass within the time limit, though it may be tight.
• For Python: performance varies widely by implementation; using arrays from the numpy library instead of lists, together with the Sieve of Eratosthenes, can still pass within reasonable time and memory limits.

Problem Description

Given an upper bound $n$ and $q$ queries, for each query output the $k$-th smallest prime number.

Input Format

The first line contains two positive integers $n, q$, representing the query range and the number of queries.

Each of the next $q$ lines contains a positive integer $k$, asking for the $k$-th smallest prime.

Output Format

Output $q$ lines, each containing a single integer as the answer.

100 5
1
2
3
4
5

2
3
5
7
11

Hint

Constraints
For $100\%$ of the testdata, $n = 10^8$, $1 \le q \le 10^6$, and it is guaranteed that the requested primes do not exceed $n$.

Data by NaCly_Fish.

Translated by ChatGPT 5