phantichthanhthuasonguyento.cpp

#include<iostream>
#include<vector>
#include<cstdlib>
//#include<conio.h>

#define long long long
#define nln '\n'

using namespace std;

vector<long> prm;

void sieve()
{
    long N = 1e4;
    vector<bool> s(N, 0);
    for (long i = 2; i <= N; ++i)
        if (!s[i]){
            prm.push_back(i);
            for (long j = 2*i; j <= N; j += i)
                s[j] = 1;
        }
}


void construe(long n)
{
    long i = 0;
    while (n > 1){
        if (n % prm[i] == 0){
            cout << prm[i];
            n /= prm[i];
            if (n > 1)
                cout << "*";
        }
        else{
            if (prm[i+1]*prm[i+1] > n){
                cout << n;
                n = 1;
            }
            ++i;
        }
        /*cout << "i: " << i << nln;
        cout << "prm: " << prm[i] << nln;
        cout << "n: " << n << nln;*/
//      getch();
    }
    cout << nln;
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0)->sync_with_stdio(0);
    //freopen("input.inp", "r", stdin);
    //freopen("output.out", "w", stdout);
    sieve();
    long T;
    cin >> T;
    while (T--){
        long n;
        cin >> n;
        construe(n);
    }
    return 0;
}