[알고리즘] 소인수분해 | 프로그래머스 | 파이썬으로 소인수분해 하기

문제 설명

소인수분해란 어떤 수를 소수들의 곱으로 표현하는 것입니다. 예를 들어 12를 소인수 분해하면 2 * 2 * 3 으로 나타낼 수 있습니다. 따라서 12의 소인수는 2와 3입니다. 자연수 n이 매개변수로 주어질 때 n의 소인수를 오름차순으로 담은 배열을 return하도록 solution 함수를 완성해주세요.

 

제한사항

• 2 ≤ n ≤ 10,000

 

입출력 예

n	result
12	[2, 3]
17	[17]
420	[2, 3, 5, 7]

 

코드

def solution(n):
    i = 2
    i_list = []
    
    while i <= n:
        if n % i == 0:
            i_list.append(i)
            n /= i
        else:
            i += 1
    
    result = list(set(i_list))
    
    return sorted(result)

• 소인수 분해는 소수의 곱셈으로 제안한 수를 표현하는 것이다
• 따라서 소수(2부터 시작)를 차례차례 늘려나가며, 소수로 나누어지는지 판단하고 그렇지 않으면 소수의 숫자를 증가시키도록 한다
• 여기서 소수가 아닌 수로 나누어질 걱정은 하지 않아도 된다! 왜냐하면 소수가 아닌 수를 구성하는 작은 소수가 이미 이전에 여러번 나누어지기 때문이다
  예) i=4로 한 번 나누어질 것들은 모두 i=2에서 두 번으로 나누어지기 떄문에!
• set을 이용하여 하나의 소수로 여러번 나누어진 경우의 중복을 제거한 뒤, 이를 다시 list로 변환시켜 정렬하여 반환한다