TLE求调

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
#define int long long
bool check(int x) {
	if (x < 2) return false;
	if (x == 2) return true;
	for (int i = 2; i * i <= x; i++)
		if (x % i == 0) return false;
	return true;
}
signed main() {
	int n; cin >> n;
	string result = ""; int cnt = 0;
	if (check(n)) {
		cout << n << endl;
		return 0;
	}
	for (int i = n; i >= 2; i--) if (check(i) && n % i == 0) {
		string tmp;
		vector<int> primes;
		while (n % i == 0 && n != 1) {
			primes.push_back(i);
			n /= i;
		}
		if (primes.size() == 1) {
			tmp = to_string(primes[0]);
			reverse(tmp.begin(), tmp.end());
		} else {
			string power = to_string(primes.size()); reverse(power.begin(), power.end());
			string base = to_string(primes[0]); reverse(base.begin(), base.end());
			tmp += (power + "^" + base);
		}
		if (cnt != 0) result += " * ";
		result += tmp;
		cnt++;
	}
	if (cnt != 1) reverse(result.begin(), result.end());
	cout << result;
	return 0;
}