소인수분해

https://school.programmers.co.kr/learn/courses/30/lessons/120852

프로그래머스

---

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

• 12를 소인수분해하면 2 * 2 * 3 입니다. 따라서 [2, 3]을 return합니다.

입출력 예 #2

• 17은 소수입니다. 따라서 [17]을 return 해야 합니다.

입출력 예 #3

• 420을 소인수분해하면 2 * 2 * 3 * 5 * 7 입니다. 따라서 [2, 3, 5, 7]을 return합니다.

---

숫자를 소인수 분해하는 문제입니다.

소인수 분해는 항상 난감한 문제죠. 생각보다 소수를 구하는 게 쉽지 않습니다.

 

가장 처음에 생각해낸 방법은 tar라는 나누는 값을 설정하고, n을 tar로 나눴을 때 나머지가 생길 때까지 반복하는 구조로 코드를 짜면 되지 않을까 했습니다.

이 방법으로 작성한 코드는 아래와 같습니다.

def solution(n):
    # 소인수를 집합으로 저장
    answer = set()
    # 시작값 2로 설정
    tar = 2
    # n이 1이 될 때까지 반복
    while n > 1:
        # 나머지가 남는다면 tar 증가
        if n % tar:
            tar += 1
        # 나머지가 남지 않는다면
        else:
            # n을 tar로 나누고
            n /= tar
            # answer에 추가
            answer.add(tar)
    # 집합을 리스트로 전환 후 정렬
    answer = sorted(list(answer))
    return answer

 

곰곰히 생각해보니까 굳이 n > 1로 설정하지 말고, tar를 기준으로도 while문 반복을 끝낼 수도 있었습니다.

n의 약수를 셀 때 sqrt(n)까지만 반복하면 되는 것처럼, 이 문제에서도 tar ** 2로 종료 조건을 설정할 수 있습니다.

def solution(n):
    # 초기값 설정
    answer, tar = [], 2
    # tar가 sqrt(n)까지만 반복
    while tar ** 2 <= n:
        # 나머지가 남는다면 tar 증가
        if n % tar:
            tar += 1
        # 나머지가 남지 않는다면(배수라면)
        else:
            # tar 추가
            answer.append(tar)
            # 해당 배수가 남지 않을 때까지 반복
            while n % tar == 0:
                n //= tar
    # 남아있는 소수가 있는 경우 (n > 1 이면 그 자체가 소수)
    if n > 1:
        answer.append(n)
        
    return answer

좀 더 효율적으로 작성해본 코드는 다음과 같습니다.

tar의 반복 범위를 줄였고, 한 번 소인수인 것이 확인되면 해당 소인수가 사라질 때까지 반복하도록 했습니다.

 

마지막에는 n > 1 조건을 설정해줬는데요, 이 조건은 n 자체가 소수일 때를 위해서입니다.

17 같은 케이스도 tar가 17까지는 진행하지 못하기 때문에 이렇게 따로 추가를 해줘야 합니다.

 

소인수 문제는 언제나 생각할 게 많은 문제 같네요.