#B4170. B4170 [BCSP-X 2024 6 月小学高年级组] 最小质因子
B4170 [BCSP-X 2024 6 月小学高年级组] 最小质因子
B4170 [BCSP-X 2024 6 月小学高年级组] 最小质因子
入门 | 洛谷题组 | 原题链接
题意
给 组正整数 ,求各自的最小质因子。从 2 试除;若试到 都不能整除,则 本身是质数(样例里有 43607027731 这样的数,必须剪枝)。
输入格式
第一行 个整数 ,代表有 组数据。
接下来 行,每行 个整数 。
输出格式
输出 行,每行 个整数 代表答案。
样例
样例 1:
# 输入
14
36
2
3
49
81
35
12
89
16
100
967217
917597
185971
43607027731
# 输出
2
2
3
7
3
5
2
89
2
2
37
571
185971
43607027731
数据范围
n 可达 43607027731。
提示
考点:试除找最小质因子 + 剪枝。易错点:不要写 while(n%p!=0) p++——若 n 是大素数会试到 n 本身(436 亿次)而超时;正确写法是 while(p*p<=n && n%p!=0) p++,循环结束后若 p*p>n 则 n 本身是质数,答案就是 n。