[파이썬 | 알고리즘 문제해결전략] 간단한 형태의 소인수 분해 알고리즘

[예제 4.6]

 

import sys
read = sys.stdin.readline
 
def pprint(sortedNum):
    N = len(sortedNum)
 
    sortedNum.append(sortedNum[-1]+1)
    ans = []
    ret = ''
    oldI = -1
    for i in range(N):
        if sortedNum[i+1] != sortedNum[i]:
            ans.append([sortedNum[i], i-oldI])
            oldI = i
    sortedNum.pop()
    
    for a in ans[:-1]:
        ret += ('%d^%d +' % (a[0], a[1]))
    ret += ('%d^%d' % (ans[-1][0], ans[-1][1]))
 
    print(ret)
 
def factor(n):
    if n == 1: return [1]
    ret = []
    for i in range(2, n+1):
        while n % i == 0:
            ret.append(i)
            n /= i
 
    pprint(ret)
 
    return ret
 
if __name__ == '__main__':
    print(factor(360))