这道题更像是结论题，因为他要推一个小结论，才能做出这道题。
大概思路是先打个素数表，存到数组 \(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;
}