a010: 因數分解

http://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