[zerojudge] a010: 因數分解

# a010 因數分解 python
import sys
import math
'''
題目說 n <= 1000000
而  n 的質因數 <= sqrt(n)
所以先來建立一個質數表
'''
limit = 1000000
u = int(math.sqrt(limit))
sieve = [0, 0, 2, 3] + [1] * (u - 4)
prime = [2]
for i in range(3, u, 2):
    if(sieve[i] == 0): 
        # sieve[i] 為 0 表示被篩掉了    
        continue
    prime.append(i)
    for j in range(i * i, u, i): 
        sieve[j] = 0
# 你可以 print(prime) 來核對
# print(prime)  

def fact(n):
    r = []
    k = math.sqrt(n)
    for x in prime:
        if(x > k): break
        # 檢查到 n 的平方根
        c = 0
        while(n % x == 0):
            c += 1
            n //= x
        if(c): r.append([x,c])
        # c 是試除的次數        
    if(n > 1): r.append([n,1])
    # 剩餘的數 > 1 必定是質因數
    return r

def op(z):
    if(z[1] == 1): return str(z[0])
    return '{}^{}'.format(z[0], z[1])
    
# 主程式    
for s in sys.stdin:
    n = int(s)
    f = fact(n) # 先分解
    # print(f) 看結果對不對
    r = list(map(op, f))
    print(' * '.join(r))
    '''
    假設 n = 100
    fact(n) = [[2, 2], [5, 2]]
    r = ['2^2', '5^2']
    '''