第1题-gcd

ID: 1000

Difficulty: 2

所属公司 : 美团

时间 :2024年8月17日

题目描述

小乖对 $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$ ，所以我们只需要筛一次素数，然后再判断即可。