这道题更像是结论题，因为他要推一个小结论，才能做出这道题。
大概思路是先打个素数表，存到数组 $a$ 内， $cnt$ 是素数表的最后一个元素的下标。之后循环 $M$ 次去输入 $N$，每次输入 $N$ 之前都要定义两个变量，分别是 $mx$，存 $n - p \cdot x$ 的最大值，$ans$ 则是当 $n - p \cdot x$ 最大时存储 $x$ 用的，之后开始循环，定义循环变量 $j$，从 $1$ 开始，循环至 $cnt$，但是别忘了，我们还要设立一个循环边界，那就是 $a_{j}$ 必须小于等于 $N$，如果没有写上，答案肯定会错误。循环内只要写出 $n - p \cdot x$ 的值是否大于 $mx$，如果大于，则更新 $mx$ 的值，并把 $ans$ 设为目前的 $x$。等到循环结束后，则可以输出 $ans$ 并换行。
之后我们来简化 $n - p \cdot x$，其中 $n$ 是我们变量里的 $N$，$x$ 是个素数，所以肯定是 $a_{j}$，之后我们要用一个式子来表达 $p$，如果能表达出来，这道题才有被解决的希望。
题目中给出了一个不显眼的式子，$p \cdot a_{j} \le n < (p + 1) \cdot a_{j}$，你可能误认为这是一个数据范围，过滤掉了这个信息，但是我们却要用这个式子去推导 $p$ 的表达式。下面我们就开始推导。
$\because p \cdot a_{j} \le N < (p + 1) \cdot a_{j}$
$\therefore\frac{N}{a_{j}} - 1 < p \le \frac{N}{a_{j}}$
$\because p \in Z$
$\therefore p = \frac{N}{a_{j}}$
这样，我们终于得出了结论，$p = \frac{N}{a_{j}}$ 是恒成立的，我们把它代入到我们的代码中就可以得出正确结果了。
打素数表可以不用欧拉筛，因为这道题的数据范围不大，而且时限也放得比较宽，所以我们可以用暴力做法来存素数，我们只要打出前一万个素数就可以了。下面我们放出代码。
#include <iostream>
using namespace std;
int maxx = 10000, M, a[1000001], cnt = 0;
bool is_prime(int x){
if(x == 1) return false;
for(int i = 2; i * i <= x; i++) if(x % i == 0) return false;
return true;
}
int main(){
for(int i = 1; i <= maxx; i++) if(is_prime(i)) a[++cnt] = i;
cin >> M;
for(int i = 1; i <= M; i++){
int N, mx = 0, ans = 0;
cin >> N;
for(int j = 1; j <= cnt && a[j] <= N; j++){
if(N - (N / a[j]) * a[j] > mx){
mx = N - (N / a[j]) * a[j];
ans = a[j];
}
}
cout << ans << endl;
}
return 0;
}