Linear Sieve

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

typedef long long ll;
#define pb push_back

int main() {
    const int n = 1e5;
    int lp[n+1];
    vector<int> pr;

    for (int i = 2; i<=n; i++)
    {
        if (lp[i]==0)
        {
           lp[i] = i;
           pr.pb(i);
        }

        for (int j = 0; j<pr.size() && pr[j]<=lp[i]; i*pr[j]<=n; j++)
            lp[ i*pr[j] ] = pr[j];
    }

    // factorzation
    int a; cin >> a;
    while (a!=1)
    {
        cout << lp[a] << ' ';
        a/=lp[a];
    }
}