B3871,Python代码全部TLE

a=int(input(""))
#print(a,"=",end="")
list=[]
def prime(n):#质数判断，时间复杂度为O(n)
    for x in range(2,n):
        if n%x==0:
            return 0
    return 1
for i in range(2,a+1):
    #从2开始依次循环测试各个质数
    res=prime(i)
    if res==1:
        while a%i==0:
            #将该质因数全部除掉
            list.append(i)
            a/=i
            a=int(a)#返回整数
i=1
while i!=len(list)+1:
    if list.count(list[i-1])!=1:
        print(str(list[i-1])+"^"+str(list.count(list[i-1])),end="")#指数不为1
    else:
        print(list[i-1],end="")#指数为1
    i+=list.count(list[i-1])
    if i!=len(list)+1:
        print(" * ",end="")#如果不是最后一项，则输出乘号