[프로그래머스] LV.0 소인수분해

문제

소인수분해란 어떤 수를 소수들의 곱으로 표현하는 것입니다. 예를 들어 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]

풀이

1. 자연수 n의 약수를 먼저 구해주고 약수에 대하여 소수인지 아닌지 판별해 준다.

def solution(n):
    answer = []
    for i in range(1, n+1):
        if n % i == 0 and i!=1 : # n의 약수, 1 제거
            if is_prime(i)==1 and i not in answer:
                answer.append(i)
    
    return answer

def is_prime(x):
    for i in range(2, x):
        if x % i == 0:
            return 2 # 소수가 아님
    return 1 # 소수임

• 먼저 자연수 n의 약수를 구해주는데 소수를 구하는 것이므로 1을 제외시켜준다.
• is_prime()이라는 함수를 정의해서 구해준 약수가 소수인지 판별해준다.
• is_prime() 함수에는 2부터 x-1 까지의 모든 수를 확인하여 x가 i로 나누었을 때 나머지 값이 0이면 소수가 아니어서 2를, 나머지 값이 0이 아니면 소수이므로 1을 반환해 준다.
• 다시 solution() 함수로 돌아와 전달 받은 n의 인자 i의 값이 소수이고 동시에 answer 배열에 없다면 answer 배열에 추가해준다.

오답노트

• 일단 자연수 n의 약수 구하는 방법부터 기억하고 저장해 두었으면 한다.

def solution(n):
    factors = []
    for i in range(1, n+1):
        if n % i == 0:
            factors.append(i)
    return factors

• 다음은 자연수 x에 대한 소수 판별법을 기억하고 저장해보도록 한다.

def is_prime_number(x):
    # 2부터 (x - 1)까지의 모든 수를 확인하며
    for i in range(2, x):
        # x가 해당 수로 나누어떨어진다면
        if x % i == 0:
            return False # 소수가 아님
    return True # 소수임

• 위 두 방법을 복합적으로 사용한 것이 오늘 문제의 풀이 방법이다.