描述
给定一个整数 N，找出它的所有质因子，并按如下格式输出：
N=p1a1×p2a2×…×pkak 注意: 如果 N=1 则输出 1=1。
在程序的实际输出时，p1a1写作：p1^a1。
其中 pk 是质因子，应按照递增顺序排列，ak 是 pk 的指数，如果 ak 为 1，则不必输出。
比如：如果N=100，那么输出：100=2^2*5^2。
再比如：如果N=20，那么输出：20=2^2*5。
输入描述
一个整数N。（N≤231-1）
输出描述
按题意输出分解结果。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| #include <bits/stdc++.h>
using namespace std;
int main() {
long long n;
cin >> n;
long long tmp = n;
map<long long, int> m;
if (n == 1) {
cout << "1=1";
return 0;
}
for (long long i = 2; i * i <= n; i++) {
while (n % i == 0) {
m[i]++;
n /= i;
}
}
if (n > 1) {
m[n]++;
}
cout << tmp << "=";
bool first = true;
for (auto &i : m) {
if (!first) {
cout << "*";
}
first = false;
if (i.second > 1) {
cout << i.first << "^" << i.second;
} else {
cout << i.first;
}
}
return 0;
}
|