BOJ 11653번 : 소인수분해

안녕하세요. 지난 포스팅의 BOJ 2581번 : 소수에서는 소수를 구하는 알고리즘을 활용해서 주어진 범위 내에서 소수의 합과 가장 작은 소수를 구하는 방법에 대해서 알아보았습니다. 오늘은 소인수분해를 구현해보도록 하겠습니다. 

 

 

완벽한 코딩은 존재하지 않습니다. 제가 제출한 코드 역시 마찬가지고 그저 참고만 해주시길 바랍니다. 

 

핵심 포인트

• 기본 구현능력
• 소인수분해의 정의

 

제출 코드

N = int(input())

for p in range(2, N + 1) :
    while N % p == 0 :
        print(p)
        N //= p

 

해설

먼저 어떤 정수 $N$이 입력되면 해당 정수에 대한 소인수분해한 결과를 한 줄씩 출력해주면 됩니다. 방법은 간단합니다. 어차피 1은 모든 정수들에 대해서 나누어떨어지기 때문에 생략하고 2부터 $N$까지 모든 수들을 검사합니다. 이때, 같은 수로 계속 나누어떨어지는 경우가 있을 겁니다. 예를 들엇, 72같은 경우에는 2, 2, 2, 3, 3으로 소인수분해가 되기 때문에 더 이상 2로 나누어떨어지지 않을 때까지 2를 출력한 뒤 2로 나누었을 때의 몫을 출력하는 것이죠. 

 

참고자료 및 그림출처

백준 코딩 문제