TLE了

#include<bits/stdc++.h>
using namespace std;
bool prime(int x)
{
	if(x<2)
	{
		return 0; 
	}
	if(x==2)
	{
		return 1;
	}
	for(int i=2;i*i<=x;i++)
	{
		if(x%i==0)
		{
			return 0;
		}
	}
	return 1;
}
int f(int x)
{
	int cnt=0;
	bool pd=1;
	for(int i=2;i<=x;i++)
	{
		if(prime(i))
		{
			cnt=0;
			while(x%i==0)
			{
				x/=i;
				cnt++;
			}
			if(pd==1)
			{
				if(cnt==1)
				{
					printf("%d",i);
				}
				if(cnt>=2)
				{
					printf("%d^%d",i,cnt);
				}			
			}
			else
			{
				if(cnt==1)
				{
					printf("*%d",i);
				}
				if(cnt>=2)
				{
					printf("*%d^%d",i,cnt); 
				}				
			}
			pd=0;
		}
	}
}
int main()
{
	int n;
	scanf("%d",&n);
	f(n);
	return 0;
}