本题就是基础课的模板再特殊处理下输出即可

复习下基础课模板：

有个性质：x中最多只含有一个大于sqrt(x)的因子。证明通过反证法：如果有两个大于sqrt(x)的因子，那么相乘会大于x，矛盾。证毕

于是我们发现最多只有一个大于sqrt(x)的因子。先考虑比sqrt(x)小的，代码和质数的判定类似。最后如果x还是>1，说明这就是大于sqrt(x)的唯一质因子，输出即可。

算法最坏时间复杂度为O(sqrt(x))

最好时间复杂度为O(log(n)):如当$n = 2 ^k$时

/*质因数：
    每个合数都可以写成几个质数相乘的形式。其中每个质数都是这个合数的因数，叫做质因数。
    把一个合数用质因数相乘的形式表示出来，叫做分解质因数。
*/
#include <iostream>
using namespace std;

void divide(int x){
    for(int i = 2;i <= x / i;i ++){
        if(x % i == 0){//如果x % i == 0，则这个i一定是质数，证明见下方
            int e = 0;//记录指数 exponent
            while(x % i == 0){
                e ++;
                x /= i;
            }
            printf("%d %d\n",i,e);
        }
    }
    //如果x还没有被除尽，说明x有大于sqrt(x)的质因数，单独处理该数即可
    //如122 = 2 * 61，sqrt(122)约等于11,所以61 > sqrt(122)
    if(x > 1){
        printf("%d %d\n",x,1);
    }
    printf("\n");
}
int main(){
    int n;
    cin >> n;
    while(n --){
        int x;
        scanf("%d",&x);
        divide(x);
    }
    return 0;
}

证明如果x % i == 0，则这个i一定是质数:

证明方法1：循环里面的 i 一定是一个质数：假如 i 是一个合数，那么它一定可以分解成多个质因子相乘的形式，这多个质因子一定比 i 要小，而比 i 小的数在之前的循环过程中一定是被x除完了的，所以 i 不可能是合数，只可能是质数

证明方法2：如果x % i == 0，则x为i的倍数并且x中不包含任何2 ~ i - 1之间的质因子，所以i中也不包含任何2 ~ i - 1之间的质因子，所以i为质数

本题完整代码：

n = int(input())
print(f"{n}=",end = '')

if n == 1:
    print(1,end='')# 注意特判一下1=1的情况
    exit(0)

ans = []

for i in range(2,int(n ** 0.5) + 1):
    if n % i == 0:
        e = 0
        while n % i == 0:
            e += 1
            n //= i
        ans.append([i,e])
if n > 1:
    ans.append([n,1])

first = True
for v,e in ans:
    if first:
        first = False
        if e == 1:
            print(f"{v}",end = '')
        else:
            print(f"{v}^{e}",end = '')
    else:
        if e == 1:
            print(f"*{v}",end = '')
        else:
            print(f"*{v}^{e}",end = '')