include iostream include vector using namespace std vector int lp prim

 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
#include <iostream>
#include <vector>
using namespace std;
vector <int> lp,
primes;
vector <pair <int, int>> V; // число факторизации / максимальная степень
vector <int> D;
int val;
void func (int pos, int val) {
if (pos == V.size ()) {
D.push_back (val);
return;
}
for (int i = 0; i < V[pos].second + 1; ++i) {
func (pos + 1, val);
val *= V[pos].first;
}
}
int main () {
int n;
cin >> n;
lp.assign (n + 1, 0);
for (int i = 2; i <= n; ++i) {
if (!lp[i]) {
lp[i] = i;
primes.push_back (i);
}
for (int j = 0; j < primes.size () && i * primes[j] <= n && lp[i] >= primes[j]; ++j)
lp[i * primes[j]] = primes[j];
}
cout << "primes number" << endl;
for (int i = 0; i < primes.size (); ++i)
cout << primes[i] << " ";
cout << endl;
cin >> val;
while (val > 1) {
V.push_back (make_pair (lp[val], 0));
int x = val;
for ( ; val % lp[x] == 0;) {
V[V.size () - 1].second++;
val /= lp[x];
}
}
for (int i = 0; i < V.size (); ++i)
cout << V[i].first << " " << V[i].second << endl;
func (0, 1);
for (int i = 0; i < D.size (); ++i)
cout << D[i] << " ";
cout << endl;
system ("pause");
return 0;
}