-
Notifications
You must be signed in to change notification settings - Fork 1
/
uva_583.cpp
85 lines (76 loc) · 1.69 KB
/
uva_583.cpp
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <bits/stdc++.h>
#define REP(i, a, b) for(int i = a, _b = b; i < _b; ++i)
#define FOR(i, a, b) for(int i = a, _b = b; i <= b; ++i)
#define FORD(i, a, b) for(int i = a, _b = b; i >= b; --i)
#define endl "\n"
#define newline cout << "\n"
#define puts(_xxx_) cout << _xxx_ << "\n"
#define db1(x) cout << #x << " = " << x << "\n"
#define db2(a, i) cout << #a << "[" << i << "] = " << a[i] << "\n"
using namespace std;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef long long llong;
const int MX = 1E5+7;
bool isPrime[MX];
vector<int> primes;
void sieve () {
memset(isPrime, true, sizeof isPrime);
FOR(i, 2, sqrt(MX)) {
if(isPrime[i]) {
for(int j = i*i; j < MX; j += i) {
isPrime[j] = false;
}
}
}
REP(i, 2, MX) {
if(isPrime[i]) {
primes.push_back(i);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
#ifndef Home
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
sieve();
int n;
while(cin >> n and n) {
int n1 = abs(n);
vector<ii> ans;
for(int prime: primes) {
if(prime > n1) break;
if(n1%prime == 0) {
int cnt = 1;
for(n1 /= prime; n1 % prime == 0; n1 /= prime, cnt++);
ans.push_back(ii(prime, cnt));
}
if(n1 == 1) break;
}
if(n1 != 1) {
ans.push_back(ii(n1, 1));
}
if(ans.size() == 0) {
cout << n << " = " << n << endl;
continue;
}
if (n < 0) {
cout << n << " = -1 x ";
}
else {
cout << n << " = ";
}
cout << ans[0].first;
ans[0].second--;
REP(i, 0, ans.size()) {
REP(j, 0, ans[i].second) {
cout << " x " << ans[i].first;
}
}
newline;
}
return 0;
}