[프로그래머스] 소인수분해(Python)

프로그래머스 - 소인수분해

풀이

• 에라토스테네스의 체 알고리즘 활용
• i = 2부터 n까지 증가
• n을 i로 나누는데, 나누어 떨어지면 인수, 그렇지 않으면 i값 증가하며 인수 찾기
• 인수는 prime set에 저장(중복 제거)

코드

def solution(n):
    prime = set()
    
    i = 2
    while i <= n:
        if n % i == 0:
            n /= i
            prime.add(i)
        else:
            i += 1

    return sorted(list(prime))