# Участник:ZhenyaStrelkova/BREAKING

Перейти к: навигация, поиск
```#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int maximum = 1000007;

int spf[maximum];

// Calculating SPF (Smallest Prime Factor) for every
// number till MAXN.
// Time Complexity : O(nloglogn)
void sieve() {
spf[1] = 1;
for (int i = 2; i < maximum; i++)

// marking smallest prime factor for every
// number to be itself.
spf[i] = i;

// separately marking spf for every even
// number as 2
for (int i = 4; i < maximum; i += 2)
spf[i] = 2;

for (int i = 3; i * i < maximum; i++) {
// checking if i is prime
if (spf[i] == i) {
// marking SPF for all numbers divisible by i
for (int j = i * i; j < maximum; j += i)

// marking spf[j] if it is not
// previously marked
if (spf[j] == j)
spf[j] = i;
}
}
}

// A O(log n) function returning primefactorization
// by dividing by smallest prime factor at every step
vector<int> getFactorization(int x) {
vector<int> ret;
while (x != 1) {
ret.push_back(spf[x]);
x = x / spf[x];
}
return ret;
}

// driver program for above function
int main() {
// precalculating Smallest Prime Factor
sieve();
int n, x;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> x;
cout << "Case " << i + 1 << ": ";
vector<int> p = getFactorization(x);
sort(p.begin(), p.end());
p.erase(unique(p.begin(), p.end()), p.end());
for (int j = 0; j < p.size() - 1; j++)
cout << p[j] << " ";
cout << *p.rbegin() << endl;
}
return 0;
}```