867.分解质因数

时/空限制：1s / 64MB

题目描述

给定\(n\)个正整数\(a_i\)，将每个数分解质因数，并按照质因数从小到大的顺序输出每个质因数的底数和指数。

输入格式

第一行包含整数\(n\)。

接下来\(n\)行，每行包含一个正整数\(a_i\)。

输出格式

对于每个正整数\(a_i\)，按照从小到大的顺序输出其分解质因数后，每个质因数的底数和指数，每个底数和指数占一行。

每个正整数的质因数全部输出完毕后，输出一个空行。

数据范围

\(1 \le n \le 100\), \(1 \le a_i \le 2\times10^9\)

输入样例

2
6
8

输出样例

2 1
3 1

2 3

解释：第一行输入 \(2\)，说明接下来两行输入两个数，第一个输入是 \(6\)，输出结果为两行，每行的含义是：底数为数字 \(2\)，指数为 \(1\)，底数为数字 \(3\)，指数为 \(1\)，即 \(6 = 2^1 \times 3^1\)。第二个输入是 \(8\)，则输出结果为一行，含义是：底数为数字 \(2\)，指数为 \(3\)，即 \(8 = 2^3\)。

代码

// 暴力枚举
void divide(int n) {
	for(int i = 2; i <= n; ++i) {
		if(n % i == 0) {
			int s = 0;
			while(n % i == 0) {
				n /= i;
				++s;
			}
			printf("%d %d\n", i, s);
		}
	}
    printf("\n");
}

前文 「866.试除法判定质数」谈及到「质数性质」可用于优化本题，可知：输入数字 \(n\) 中最多只包含一个大于 \(\sqrt{n}\) 的质因子（假设某数分解出来的两个质因子均大于 \(\sqrt{n}\)，则乘积就会大于 \(n\)，那这显然不成立）。因此枚举时，可先枚举 \(\le \sqrt{n}\) 的质因子，优化代码如下，将for循环范围改至n/i：

// 优化版本O(sqrt(n))
void divide(int n) {
	for(int i = 2; i <= n / i; ++i) { // 优化为 i <= n / i
		if(n % i == 0) {
			int s = 0;
			while(n % i == 0) {
				n /= i;
				++s;
			}
			printf("%d %d\n", i, s);
		}
	}
	// 质数最多存在一个大于sqrt(n)的质因子
	// 例如：6 = 2 * 3，sqrt(6) = 2.44949，存在一个大于sqrt(6)的质因子3
    if(n > 1) printf("%d %d\n", n, 1);
    printf("\n");
}

本题优化版本相比「866.试除法判定质数」优化版本，时间复杂度不同，866题优化版本时间复杂度一定为 \(\text{O}(\sqrt{n})\)；本题优化版本有可能当 \(i = 2\) 成立后，进入while执行完毕，直接跳出循环，导致最快时间复杂度为 \(\text{O}({\log n})\)，因此本题优化版本时间复杂度介于 \(\text{O}({\log n})\) 和 \(\text{O}(\sqrt{n})\) 之间。

算法	时间复杂度
判断是否为质数「866.试除法判定质数」优化版本	\(\text{O}(\sqrt{n})\)
分解某数为多个质因数乘积（本题优化版本）	介于 \(\text{O}({\log n})\) 和 \(\text{O}(\sqrt{n})\) 之间

补充

1. 算术基本定理（唯一分解定理） \(\forall\) 大于 \(1\) 的正整数 \(N\)，若 \(N\) 不为质数，都可以唯一分解成有限个质数的乘积。\(N = P_1^{a_1} \times P_2^{a_2} \times ... \times P_n^{a_n}\)，这里 \(P_1 < P_2 < ... < P_n\) 均为质数，指数 \(a_i\) 是正整数。
2. 算法思路：枚举 \(i\) 从 \(2\) 到 \(\sqrt{n}\)，如果 n % i == 0，就一直用 \(n\) 除以 \(i\)，求出来 \(i\) 的指数，并用 \(s\) 来记录；若最终 \(n > 1\)，则此时的 \(n\) 是大于 \(\sqrt{n}\) 的那个唯一的质因数；