simple-prime-factorization
Source: hackerearth
Difficulty: EASY

Surya loves to play with primes. One day, he asked his friend don to print any number in the form of multiple of prime factors. Help don in solving the problem. 

Input
The first line will contain an integer t (1 ≤ t ≤ 10^6) denoting number of test case. 
For each test case, you will be given an integer n (2 ≤ n ≤ 10^6).

Output
Print a string showing prime factors which should look like :
2^e1 * p2^e2 * .........* pk^ek 
where p1, p2, ...., pn are the prime factors and e1, e2, ....., en is the degree of corresponding prime factor.

Note: power of 2 should always be given.
For a prime number , only 2^0 is printed.

SAMPLE INPUT
3
32
100
9085

SAMPLE OUTPUT
2^5
2^2*5^2
2^0*5^1*23^1*79^1


def primes(n):
	primfac = []
	d = 2
	while d*d <= n:
		while (n % d) == 0:
			primfac.append(d)
			n //= d
		d += 1
	if n > 1:
	   primfac.append(n)
	return primfac
t = int(input())
for _ in range(t):
	l = []
	ans = []
	d = {}
	sd = {}
	d[2] = 0
	n = int(input())
	l = primes(n)
	for i in l:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	if(len(d)==2 and d[2]==0):
		print('2^0')
	else:
		sd = sorted(d.items())
		for k,v in sd:
			ans.append("%d^%d"%(k,v))
		print("*".join(ans))
		
	



from math import sqrt
def bs(a,t):
	low=0
	high=len(a)-1
	while low<=high:
		mid=(low+high)/2
		if t==a[mid]:
			#print mid
			return True
		elif t<a[mid]:
			high=mid-1
		else:
			low=mid+1
	return False
def sieve(n):
	primes = list(range(3, n + 1, 2)) # primes above 2 must be odd so start at three and increase by 2
	for base in range(len(primes)):
		if primes[base] is None:
			continue
		if primes[base] > sqrt(n): # stop at sqrt of n
			break

		for i in range(base + (base + 1) * primes[base], len(primes), primes[base]):
			primes[i] = None
	primes.insert(0,2)
	return [_f for _f in primes if _f]


arr=sieve(1000000)

def primef(n):
	art=[]
	sart=[]
	temp=0
	while n%2==0:
		art.append(2)
		temp+=1
		n=n/2
	sart.append(str('2^')+str(temp))
	sart.append("*")
	
	for i in range(3,int(n**0.5)+1,2):
		temp=0
		while n%i==0:
			art.append(i)
			temp+=1
			n=n/i
		if temp>0:
			sart.append(str(i)+str('^')+str(temp))
			sart.append("*")
	if n>2:
		art.append(n)
		sart.append(str(n)+str('^')+str(1))
		sart.append("*")
	return sart
		


for _ in range(eval(input())):
	n=eval(input())
	if bs(arr,n):
		print(str("2^0"))
	else:
		final=primef(n)
		print(''.join(final)[:-1])


from math import sqrt;
A=[1]*1000005;	B=[2];
for i in range(3,1001,2):
	if A[i]:
		for j in range(i*i,1000001,2*i):
			A[j]=0;
for i in range(3,1000001,2):
	if A[i]:	B.append(i);

for i in range(int(input())):
	n=int(input());
	if A[n] and n&1:	print("2^0");	continue;
	else:
		s=sqrt(n);	i=0;	st='';
		while B[i]<=s and n>1:
			ct=0;
			while n%B[i]==0:	n/=B[i];	ct+=1;
			if B[i]==2:	st+="2^"+str(ct)+"*";
			elif ct:	st+=str(B[i])+"^"+str(ct)+"*";
			i+=1;
		if n>1:	st+=str(n)+"^1*";
		print(st[:-1]);


def CheckIfProbablyPrime(x):
	return (2 << x - 2) % x
def primes(n):
	primfac = []
	d = 2
	while d*d <= n:
		while (n % d) == 0:
			primfac.append(d)
			n //= d
		d += 1
	if n > 1:
	   primfac.append(n)
	return primfac
for i in range(eval(input())):
	a=eval(input())
	s=""
	s1=""
	if(a==2 or CheckIfProbablyPrime(a)==1):
		print('2^0')
		continue;
	else:
		l=primes(a)
		l1=list(set(l))
		l1.sort()
		if(l.count(2)==0):
			s='2^0*'
		for j in range(0,len(l1)):
			s+=str(l1[j])+'^'+str(l.count(l1[j]))+'*'
	for k in range(0,len(s)-1):
		s1+=s[k]
	print(s1)