题目描述

小乖对 $gcd$ (最大公约数) 很感兴趣, 他会询问你$t$次。 每次询问给出一个大于 $1$ 的正整数 $n$,

思路：数论

所有大于1的合数均可以表示为若干个素数的积，即$x=p_{1}^{k_1}*p_{2}^{k_2}*...*p_{n}^{k_n}$

所以我们只需要找到$x$的一个素因子$k$，那么答案即为$x/k$

由于$n$最大为$10^5$，所以我们只需要筛一次素数，然后再判断即可。