integer factorization

#include <bits/stdc++.h>

using namespace std ;
#define sz(s) int(s.size())
#define all(s) s.begin() , s.end()
#define getline(s) getline(cin >> ws, s)
#define cin(v) for (auto& i : v) cin >> i ;
#define cout(v) for (auto& i : v) cout << i << " "
#define pb(x) push_back(x)
#define ll long long
#define ull unsigned long long
#define Mod 1'000'000'007
#define INF 2'000'000'000
#define Num_of_Digits(n) ((int)log10(n)+1)
#define fixed(n) fixed << setprecision(n)
#define imin INT_MIN
#define imax INT_MAX
#define Time cerr << "Time Taken: " << (float)clock() / CLOCKS_PER_SEC << " Secs" << "\n" ;

void ABDEL3AL () {
    ios_base::sync_with_stdio(false); cin.tie(nullptr) , cout.tie(nullptr) ;
#ifndef ONLINE_JUDGE
    freopen("input.txt" , "r" , stdin) , freopen("output.txt" , "w" , stdout) ;
#endif
    Time
}

vector < ll > prime_factorization (ll n) {
    vector < ll > factors ;
    while (n % 2 == 0) factors.push_back(2) , n /= 2 ;
    for (int i = 3; i <= n; i += 2)
        while (n % i == 0) factors.push_back(i) , n /= i ;
    if (n > 2) factors.push_back(n) ;
    return factors ;
}


int main() {
    ABDEL3AL() ;
    ll n ;
    while (true) {
        cin >> n ;
        if (!n) return 0 ;
        map <ll , ll> freq ;
        vector < ll > v = prime_factorization(n) ;
        for (auto& i : v) freq[i]++ ;
        for (auto& i : freq) cout << i.first << "^" << i.second << " " ;
        cout << "\n" ;
    }
    return 0;
}