View Code of Problem 103

#include<iostream>
#include<string>
#include<cmath>
#include<cstring>
#include<vector>
#include<iomanip>
#include<cstdio>
#include<algorithm>
#include<ctype.h>
using namespace std;
int sh(long long n)
{
	if (n == 0 || n == 1)
		return 0;
	if (n == 2)
		return 1;
	for (int i = 2;i < (int)sqrt(n) + 1;i++)
	{
		if (n%i == 0)
			return 0;
	}
	return 1;
}
int main()
{
	int n;
	cin >> n;
	while (n--)
	{
		vector<long long>res;
		long long int a;
		cin >> a;
		long long z = a;
		if (sh(a) == 1)
		{
			cout << a << endl;
			continue;
		}
		vector<long long >num(z,0);
		while (sh(a) == 0)
		{
			for (int i = 2;i < z;i++)
			{
				if (num[i] == 0)
				{
					for (int j = i + i;j < z;j = j + i)
					{
						num[j] = 1;
					}
					if (a%i == 0)
					{
						a = a / i;
						res.push_back(i);
						i = 1;
					}
				}
				if (sh(a) == 1)
					break;
			}
		}
		res.push_back(a);
		int flag = 0;
		int flag1 = 0;
		int i;
		for (i = 0;i < res.size() - 1;i++)
		{
			int cnt = 1;
			if (res[i] == res[i + 1])
			{
				while ((res[i] == res[i + 1]))
				{
					i++;
					cnt++;

					if (i >= res.size() - 1)
					{
						flag1 = 1;
						break;
					}
				}
			}
			if (flag == 0)
				flag = 1;
			else
				cout << "*";
			if (cnt == 1)
			{
				cout << res[i];
			}
			else
			{
				cout << res[i] << "^" << cnt;
			}
		}
		if (flag1 == 0)
			cout << "*" << res[res.size() - 1];
		cout << endl;
	}

}