#sx003. 分解质因数
分解质因数
分解质因数
题目描述
给定一个正整数 n,请将其分解为若干个质数的乘积,并按从小到大顺序输出所有质因数(可重复输出,即每个质因数出现几次就输出几次)。
算法概念
分解质因数(Prime Factorization)是将一个正整数表示为若干个质数乘积的过程。每个合数都可以唯一地分解为质因数的乘积(算术基本定理)。常用的分解方法为短除法:从最小的质数开始尝试整除,若能整除则记录该质数,并用商继续分解,直到商为 1。
算法原理与步骤
- 从最小的质数 2 开始,依次尝试整除当前数 n。
- 若当前数 i 能整除 n(即 n % i == 0),则 i 是 n 的一个质因数,输出 i,并将 n 更新为 n / i,继续用 i 尝试整除新的 n。
- 若当前数 i 不能整除 n,则 i 自增 1,继续尝试下一个数。
- 重复上述过程,直到 n 变为 1,分解结束。
- 特殊性质:这种方法不需要判断 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 本身。
扩展应用:分解质因数可用于约数个数计算、欧拉函数求解等数论问题。