PrimeFactorization

#include<bits/stdc++.h>
using namespace std;
#define MAX 1000000
bool v[MAX];
int len, sp[MAX];
vector <int> ans;
void Sieve()
{
    for (int i = 2; i < MAX; i += 2)
        sp[i] = 2;//even numbers have smallest prime factor 2
    for (long long i = 3; i < MAX; i += 2)
    {
        if (!v[i])
        {
            sp[i] = i;
            for (long long j = i; (j*i) < MAX; j += 2)
            {
                if (!v[j*i])
                    v[j*i] = true, sp[j*i] = i;
            }
        }
    }
}
void factorize(long long k)
{
    int cnt=0;
    while(k>1)
    {
        int sml=sp[k];
        //ans.push_back(sml);
        //printf("%d ",sml);
        while(k%sml==0)
        {
            cnt++;
            k/=sml;
            //printf("%d ",sml);
        }
        ans.push_back(cnt);
        cnt=0;
    }
    //printf("\n");
    //return ans;
}
int main()
{
    Sieve();
    long long num,t=5;
    while(t--){
    ans.clear();
    scanf("%lld",&num);
    factorize(num);
    for(int i=0; i<ans.size();i++)
        printf("%d ",ans[i]);
        cout<<endl;
    }
    //for (int i = 0; i < 50; i++)
        //printf("%d = %d\n",i,sp[i]);

    return 0;
}