#sx003. 分解质因数

分解质因数

分解质因数

题目描述

​ 给定一个正整数 n,请将其分解为若干个质数的乘积,并按从小到大顺序输出所有质因数(可重复输出,即每个质因数出现几次就输出几次)。

算法概念

​ 分解质因数(Prime Factorization)是将一个正整数表示为若干个质数乘积的过程。每个合数都可以唯一地分解为质因数的乘积(算术基本定理)。常用的分解方法为短除法:从最小的质数开始尝试整除,若能整除则记录该质数,并用商继续分解,直到商为 1。

算法原理与步骤

  1. 从最小的质数 2 开始,依次尝试整除当前数 n。
  2. 若当前数 i 能整除 n(即 n % i == 0),则 i 是 n 的一个质因数,输出 i,并将 n 更新为 n / i,继续用 i 尝试整除新的 n。
  3. 若当前数 i 不能整除 n,则 i 自增 1,继续尝试下一个数。
  4. 重复上述过程,直到 n 变为 1,分解结束。
  5. 特殊性质:这种方法不需要判断 i 是否为质数。因为当 i 为合数时,其质因数一定小于 i,且已被之前的步骤除尽,所以合数不可能整除当前的 n,因此 i 一定是质数时才可能进入循环。

​ 举例:分解 12 的质因数。

​ 12 ÷ 2 = 6(输出 2) ​ 6 ÷ 2 = 3(输出 2) ​ 3 ÷ 3 = 1(输出 3)

​ 此时 n = 1,分解结束,得到 12 = 2 × 2 × 3。

输入格式

​ 一行一个正整数 n。

输出格式

​ 一行,输出 n 的所有质因数,按从小到大顺序输出,每个质因数出现几次就输出几次,相邻数字用空格隔开。

输入输出样例

18
2 3 3

数据规模与约定

​ 2 ≤ n ≤ 10^6

​ 时间限制:1 秒(分解质因数的时间复杂度为 O(sqrt(n)) 左右,n=10^6 时极快)

提示

​ 代码提示:

// 从最小质数 2 开始尝试
for (int i = 2; i <= n; i++) {
    // 当前 i 如果能整除 n,则 i 是质因数
    // TODO: 使用 while 循环反复除以 i,输出 i,并更新 n
    // 提示:while (n % i == 0) { cout << i << " "; n = n / i; }
}

​ 运用提示:

​ 短除法的核心是“用质数不断除”,但代码中无需显式判断 i 是否为质数。因为如果 i 是合数,它的质因数已经被更小的数除尽,此时 i 不可能整除 n,所以循环只会记录真正的质因数。

​ 注意循环条件是 i <= n,因为 n 在不断减小,当 n 变为 1 时循环自动结束。

​ 若 n 本身是质数,循环会一直执行到 i = n,输出 n 本身。

​ 扩展应用:分解质因数可用于约数个数计算、欧拉函数求解等数论问题。