a010: 因數分解

百千.IOhttp://zerojudge.tw/ShowProblem?problemid=a010

• MAX=1000000 # MAX=400000可以0.2秒AC，但那只是因為測資，大於400000的都不是質數
• is_prime=[False,False]+[True]*(MAX-1)
• primes=[]
• now=2
• while True:
• primes.append(now)
• for i in range(now*2,MAX+1,now):
• is_prime[i]=False
• now+=1
• try:
• while is_prime[now]==False:
• now+=1
• except:
• break
• while True:
• try:
• N=int(input())
• factorization=''
• for prime in primes:
• power=0
• while True:
• Q=N/prime # 只/一次，而不是%一次再/=一次
• if Q!=int(Q):
• break
• power+=1
• N=Q
• if power==1:
• factorization+=str(prime)+' * '
• elif power>1:
• factorization+=str(prime)+'^'+str(power)+' * '
• if N==1: # 測資分解到1就不再用後面的質數試圖因數分解了，可以省掉大量多此一除的除法運算時間
• break
• print(factorization[:-3])
• except:
• break