题目描述
给你 $n$ 个大于等于 $2$ 的正整数 $a_1,a_2,…,a_n$,分解它们的质因数。
样例
输入样例1:
2
6
8
输出样例1
2 1
3 1
2 3
前置知识
基本思路
首先我们证明一个定理:一个大于等于 $2$ 的正整数最多只有 $1$ 个大于 $\sqrt{n}$ 的质因数。
证:运用反证法。
设 $n$ 有两个大于 $\sqrt{n}$ 的质因数 $p,q$,则 $p\times q>\sqrt{n}\times\sqrt{n}=n$,矛盾。
所以 $n$ 最多只有 $1$ 个大于 $\sqrt{n}$ 的质因数。
所以我们仍然只需要遍历从 $2$ 到 $\sqrt{n}$ 的数就可以了。
for (int i = 2; i <= n/i; ++i) {
if (n % i == 0) {
//...
}
}
得到一个质因数后,我们需要计算这个质因数的质数是多少。
int s = 0; //s代表质因数i的指数
while (n % i == 0) //如果n还能被i整除
n /= i, s ++; //那么就再除一次,直到不能被i整除。
printf("%d %d\n", i, s);
循环完之后,如果 $n>1$,说明 $n$ 有 $1$ 个大于 $\sqrt{n}$ 的质因数,只需直接将其输出即可。
if (n > 1)
printf("%d 1\n", n);
在做循环的时候,可能会有一个问题:如果 $i$ 是合数又能整除 $n$ 的话,那么它会不会也被算进质因数里呢?
实际上不会的。因为 $i$ 的质因数都是小于 $i$ 的,而前面的循环已经把 $n$ 中所有小于 $i$ 的质数都除干净了,所以合数是不会被算进质因子里的。
完整代码
#include <iostream>
#include <cstdio>
using namespace std;
void devide(int n) {
for (int i = 2; i <= n/i; ++i) {
if (n % i == 0) {
int s = 0;
while (n % i == 0)
n /= i, s ++;
printf("%d %d\n", i, s);
}
}
if (n > 1)
printf("%d 1\n", n);
puts("");
}
int main() {
int n;
scanf("%d", &n);
while (n --) {
int t;
scanf("%d", &t);
devide(t);
}
return 0;
}