Factorial decomposition

• Time : $O(nloglogn)$
• Space : $O(factor(n))$

c++

#include <string>
using namespace std;
vector<int> prime(int n) {
    vector<int> sieve(n+1);
    vector<int> res;
    for(int i = 2; i <= n; i++) {
        if(sieve[i]) continue;
        res.push_back(i);
        for(int j = i * i; j <= n; j += i) sieve[j] = true;
    }
    return res;
}
string build(int p, int c) {
    if(c == 1) return to_string(p);
    return to_string(p)+"^"+to_string(c);
}
int helper(int n, int p) {
    int res = 0;
    for(int i = p; i <= n; i += p) {
        int x = i;
        while(x % p == 0) {
            res += 1, x /= p;
        }
    }
    return res;
}
std::string decomp(int n) {
    vector<int> primes = prime(n);
    string res = "";
    for(auto p : primes) {
        int cnt = helper(n,p);
        res += build(p,cnt) + " * ";
    }
    res.pop_back();res.pop_back();res.pop_back();
    return res;
}