Primes in numbers

• Time : $O(\sqrt{lst})$
• Space : $O(factors(lst))$

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

class PrimeDecomp
{
public:
    static std::string factors(int lst);
};
string PrimeDecomp::factors(int lst) {
    string res = "";
    auto work = [](int p, int c) {
        if(c == 1) return "(" + to_string(p) + ")";
        return "(" + to_string(p) + "**" + to_string(c) + ")";
    };
    for(int i = 2; i * i <= lst; i++) {
        if(lst % i) continue;
        int count = 0;
        while(lst % i == 0) {
            count += 1;
            lst /= i;
        }
        res += work(i,count);
    }
    if(lst != 1) res += work(lst,1);
    return res;
}