#6809. 找出范围内所有数字的最小质因数
找出范围内所有数字的最小质因数
找出范围内所有数字的最小质因数
题目描述:
输入两个整数 n 和 m,找出从 n 到 m 之间每个大于等于 2 的整数的最小质因数,并按逗号分隔输出。
如果区间中包含 1,由于 1 没有质因数,因此跳过 1,不输出任何内容。
测试数据:
-
输入:
n = 10, m = 15输出:2,11,2,13,2,3 -
输入:
n = 5, m = 7输出:5,2,7 -
输入:
n = 1, m = 3输出:2,3 -
输入:
n = 20, m = 22输出:2,3,2 -
输入:
n = 30, m = 32输出:2,31,2
解题思路:
- 遍历区间
[n,m]中的每个整数。 - 如果当前数字小于
2,直接跳过。 - 对于每个大于等于
2的整数,从2开始寻找第一个能够整除它的数。 - 第一个能够整除该数的数一定是它的最小质因数。
- 按照原区间顺序输出所有结果,并使用逗号分隔。
可以,建议在测试数据后增加一个“样例解释”部分,重点解释合数、质数以及
1的特殊情况:
样例解释
样例 1
输入:
n = 10, m = 15
需要依次求出 10、11、12、13、14、15 的最小质因数:
10 = 2 × 5,最小质因数是211是质数,所以最小质因数是1112 = 2 × 2 × 3,最小质因数是213是质数,所以最小质因数是1314 = 2 × 7,最小质因数是215 = 3 × 5,最小质因数是3
因此输出:
2,11,2,13,2,3
样例 2
输入:
n = 5, m = 7
其中:
5是质数,最小质因数是56 = 2 × 3,最小质因数是27是质数,最小质因数是7
因此输出:
5,2,7
样例 3
输入:
n = 1, m = 3
1 没有质因数,因此跳过。
2是质数,最小质因数是23是质数,最小质因数是3
因此输出:
2,3
说明:
如果一个数本身是质数,那么它的最小质因数就是它自己。例如 11 的最小质因数是 11。
如果一个数是合数,则找能够整除它的最小质数。例如 21 = 3 × 7,所以 21 的最小质因数是 3。
1 既不是质数也不是合数,并且没有质因数,因此本题中遇到 1 时直接跳过。
相关
在以下作业中: