UVa 583 - Prime Factors

583.cpp

#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define endl '\n'
#define PB push_back

typedef long long ll;
typedef vector<ll> vll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;

const int oo = ~(1<<31);

const int MAX = 1e7;
bool sieve[MAX];

vi primes;

void build() {

    for(ll i = 2; i < MAX; i++) {
        if(sieve[i]) continue;

        for(ll j=i*i; j<MAX; j+=i)
            sieve[j] = true;

        primes.PB((int)i);
    }
}

vi factor(int n) {
    vi A;
    int idx = 0;

    while(n > 1 && idx < primes.size()) {
        while(n % primes[idx] == 0) {
            A.PB(primes[idx]);
            n /= primes[idx];
        }
        idx++;
    }

    if(n > 1) A.PB(n);

    return A;
}

int main() {
    #ifndef CBDAVIDES
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
    #endif

    build();

    int n;
    while(cin >> n && n) {
        vi A = factor(n < 0 ? -n : n);
        cout << n  << " = " << (n < 0 ? "-1 x " : "");
        for(int i=0; i<A.size(); i++) {
            if(i) cout << " x ";
            cout << A[i];
        }
        cout << endl;
    }

    return 0;
}