#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<list>
#include<tuple>

using namespace std;

//소인수 분해 알고리즘 입력이 48이라면  2 2 2 2 3 으로 저장
list<int> factorization(int n) {
    if (n <= 1) return list<int>(1, 1);
    list<int> tmp;
    for (int div = 2; n > 1; div++) {
        if (n % div == 0) {
            n /= div;
            tmp.push_back(div);
            div--;
        }
    }
    return tmp;
}

int main() {
    list<int> lst1;
    list<tuple<int, int>> tplist;
    int n;


    scanf("%d", &n);
    lst1 = factorization(n);
    list<int>::iterator i = lst1.begin();
    //2 2 2 2 3으로 저장된 리스트를 2,4  3,1로 저장되는 튜플리스트로 변경
    tplist.push_back(make_tuple(*i++, 1));
    list<tuple<int, int>>::iterator k = tplist.begin();
    for (int j = 0;j < lst1.size()-1; i++,j++) {
        if (*i == get<0>(*k))
            get<1>(*k)++;
        else {
            tplist.push_back(make_tuple(*i, 1));
            k++;
        }
    }
    //튜플 리스트 출력
    k = tplist.begin();
    printf("%d = %d^%d ", n,get<0>(*k), get<1>(*k));
    k++;
    for (k ; k != tplist.end(); k++) {
        printf("* %d^%d ", get<0>(*k), get<1>(*k));
    }
    printf("\n");

    
    return 0;
}

소인수 분해 알고리즘 작성하다가 출력방식을 식으로 표현하고 싶어서 튜플 STL 사용해서 구현 해봤는데요, 원하는 결과는 나오지만 알고리즘 공부 걸음마 수준이라서 메모리나 시간복잡도를 고려하면서 작성하기 어렵네요. 더 간단하게 구현할 수 있는 방법이나 불필요한 코드 삽입된거 있으면 피드백 부탁드립니다.

실행결과:
8400
8400 = 2⁴ * 3¹ * 5² * 7¹