蓝桥杯 adv223 8-1因式分解

蓝桥杯 adv223 8-1因式分解

问题描述

设计算法,用户输入合数,程序输出若个素数的乘积。例如,输入6,输出2*3。输入20,输出2*2*5。

输入样例

120

输出样例

2*2*2*3*5

参考解答

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 <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main() {
int n;
cin >> n;
vector<int> p(n, 0);
vector<int> ip, ans;

for (int i = 2; i <= sqrt(n); i++) // 埃拉托斯特尼筛法
if (p[i] == 0) {
ip.push_back(i);
for (int j = i * i; j <= n; j+=i) {
p[j] = -1;
}
}

for (int i = 0; i < ip.size(); i++)
while (n % ip[i] == 0) {
ans.push_back(ip[i]);
n /= ip[i];
}

if (n != 1)
ans.push_back(n);

for (int i = 0; i < ans.size(); i++) {
if (i != 0)
cout << "*";
cout << ans[i];
}
return 0;
}

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×