Uva 583 Solution

#include<bits/stdc++.h>
#define N 100000
#define ll long long int
using namespace std;

int p[N+1];
vector<int>a;
void prime()
{
    ll i, j, l;
    l = sqrt(N);
    p[0] = p[1] = 1;
    a.push_back(2);
    for(i=4; i<=N; i+=2)
        p[i] = 1;
    for(i=3; i<=N; i+=2)
    {
        if(p[i] == 0)
        {
            a.push_back(i);
            for(j=i*i; j<=N; j+=i*2)
                p[j] = 1;
        }
    }
}

vector<int>b;
void factorization(ll n)
{
    ll i, j, l;
    l = sqrt(n);
    for(i=0; a[i] <= l; i++)
    {
        if(n%a[i] == 0)
        {
            while(n%a[i] == 0)
            {
                n = n/a[i];
                b.push_back(a[i]);
            }
        }
    }
    if(n > 1)
        b.push_back(n);
}

int main()
{
    prime();
    ll n, i, f;
    while(cin >> n)
    {
        if(n == 0)
            break;

        f = 0;
        if(n < 0)
        {
            f = -1;
            n = n*(-1);
        }

        factorization(n);
        if(f == -1)
            cout << "-";
        cout << n << " = ";

        if(f == -1)
            cout << f << " x ";

        for(i=0; i<b.size(); i++)
        {
            cout << b[i];
            if(i < b.size() - 1)
                cout << " x ";
        }

        b.clear();
        cout << endl;
    }

    return 0;
}