简答题
偏难
#21806
因数分解(2023.9C++五级) 时间限制:1.0 s 内存限制:128.0 MB 问题描述 每个正整数都可以分解成素数的乘积,例如:6=2×3、20=2 2…
因数分解(2023.9C++五级)
时间限制:1.0 s
内存限制:128.0 MB
问题描述
每个正整数都可以分解成素数的乘积,例如:6=2×3、20=22×5
现在,给定一个正整数N,请按要求输出它的因数分解式。
输入描述
输入第一行,包含一个正整数N。约定2≤N≤1012
输出描述
输出一行,为N的因数分解式。要求按质因数由小到大排列,乘号用星号*表示,且左右各空一格。当且仅当一个素数出现多次时,将它们合并为指数形式,用上箭头^表示,且左右不空格。
样例输入1
6
样例输出1
2 * 3
样例输入2
20
样例输出2
2^2 * 5
样例输入3
23
样例输出3
23
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <iostream>
using namespace std;
int main() {
long long N = 0;
cin >> N;
bool first = true;
for (long long p = 2; p * p <= N; p++) {
if (N % p != 0)
continue;
int cnt = 0;
while (N % p == 0) {
cnt++;
N /= p;
}
if (first) {
first = false;
} else {
cout << " * ";
}
cout << p;
if (cnt > 1)
cout << "^" << cnt;
}
if (N > 1) {
if (first) {
first = false;
} else {
cout << " * ";
}
cout << N;
}
cout << endl;
return 0;
}</pre>
这道题暂未补解析。