第1题-gcd

会员专享

请先登录，开通会员或购买该题目所属题库（美团机考编程题库），可解锁完整内容。

购买题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（美团机考编程题库），可解锁完整内容。

购买题库开通会员

思路：数论

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

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

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

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