#6809. 找出范围内所有数字的最小质因数

找出范围内所有数字的最小质因数

找出范围内所有数字的最小质因数

题目描述: 输入两个整数 nm,找出从 nm 之间每个大于等于 2 的整数的最小质因数,并按逗号分隔输出。

如果区间中包含 1,由于 1 没有质因数,因此跳过 1,不输出任何内容。

测试数据:

  1. 输入:n = 10, m = 15 输出:2,11,2,13,2,3

  2. 输入:n = 5, m = 7 输出:5,2,7

  3. 输入:n = 1, m = 3 输出:2,3

  4. 输入:n = 20, m = 22 输出:2,3,2

  5. 输入:n = 30, m = 32 输出:2,31,2

解题思路:

  1. 遍历区间 [n,m] 中的每个整数。
  2. 如果当前数字小于 2,直接跳过。
  3. 对于每个大于等于 2 的整数,从 2 开始寻找第一个能够整除它的数。
  4. 第一个能够整除该数的数一定是它的最小质因数。
  5. 按照原区间顺序输出所有结果,并使用逗号分隔。 可以,建议在测试数据后增加一个“样例解释”部分,重点解释合数、质数以及 1 的特殊情况:

样例解释

样例 1

输入:

n = 10, m = 15

需要依次求出 10、11、12、13、14、15 的最小质因数:

  • 10 = 2 × 5,最小质因数是 2
  • 11 是质数,所以最小质因数是 11
  • 12 = 2 × 2 × 3,最小质因数是 2
  • 13 是质数,所以最小质因数是 13
  • 14 = 2 × 7,最小质因数是 2
  • 15 = 3 × 5,最小质因数是 3

因此输出:

2,11,2,13,2,3

样例 2

输入:

n = 5, m = 7

其中:

  • 5 是质数,最小质因数是 5
  • 6 = 2 × 3,最小质因数是 2
  • 7 是质数,最小质因数是 7

因此输出:

5,2,7

样例 3

输入:

n = 1, m = 3

1 没有质因数,因此跳过。

  • 2 是质数,最小质因数是 2
  • 3 是质数,最小质因数是 3

因此输出:

2,3

说明:

如果一个数本身是质数,那么它的最小质因数就是它自己。例如 11 的最小质因数是 11

如果一个数是合数,则找能够整除它的最小质数。例如 21 = 3 × 7,所以 21 的最小质因数是 3

1 既不是质数也不是合数,并且没有质因数,因此本题中遇到 1 时直接跳过。