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

Материал из DISCOPAL
Перейти к: навигация, поиск

https://www.spoj.com/problems/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;
}