最小质因子
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
给定一个正整数 n,设 ,其中 都是质数,且 。给定一个正整数 ,请你计算其某最小的质因子 。
例如:
- 36 = 2 × 2 × 3 × 3,最小质因子是 2。
- 49 = 7 × 7,最小质因子是 7。
- 89 = 89,最小质因子是 89。
- 9672717 = 37 × 26141,最小质因子是 37。
输入格式
第一行有 1 个整数 T,代表一共有 T 个组数据。 对于接下来的 T 行,每行都有 1 个整数 n。
输出格式
输出 T 行,每行 1 个整数 代表答案。
14
36
2
3
49
81
35
12
89
16
100
967217
917597
185971
43607027731
输出样例1
2
2
3
7
3
5
2
89
2
2
37
571
185971
43607027731
数据范围
- 对于前 8 组数据,均有
- 对于测试组 9 ~ 14:有
- 对于测试组 15 ~ 17:有
- 对于测试组 18 ~ 20:有