프로그래머스 | 소인수분해 [파이썬 python]

프로그래머스

 

코드

def solution(n):
    answer = []
    
    x = 2
    while x <= n:
        if n % x == 0:
            if x not in answer:
                answer.append(x)
            n //= x
        else:
            x += 1
    return answer

 

주어진 수 n을 소인수분해하는 문제이다.

하지만 여기서 주의할 점은 12를 소인수분해하면 $2 \times 2 \times 3$이지만 answer에는 [2, 3]만 존재해야 한다. 2처럼 중복되는 수는 하나로만 나타내야 한다.

 

소인수분해는 1부터가 아닌 2부터 시작하므로 x = 2로 초기화해 준다.

x가 n보다 작을 경우에는 계속 반복하여 소인수를 찾는다.

 

만약 x가 n의 소인수이면 x가 answer에 존재하는지 판별한 후 없으면 answer.append(x)를 진행하고 n을 x로 나눈 몫으로 n 값을 바꿔준다.

answer에 이미 존재하면 중복해서 저장하지 않도록 추가하는 과정은 패스하고 n // x 만 진행한다.

 

더 이상 n이 x로 나누어 떨어지지 않으면 x + 1을 통해 다음 소인수를 찾는 과정을 반복한다.