[백준] 11653 : 소인수분해 (Python/파이썬)

문제 링크

https://www.acmicpc.net/problem/11653

문제

정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.

출력

N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. 
N이 1인 경우 아무것도 출력하지 않는다.

예제

입력

72

출력

2
2
2
3
3

---

정답 및 풀이

n = int(input())
i = 2
while i <= n:
    if n % i == 0:
        print(i)
        n //= i
    else:
        i += 1

1. n = int(input())
   • 사용자로부터 소인수분해할 숫자를 입력받아 정수로 변환합니다.
2. i = 2
   • 나눌 기준 숫자를 2로 초기화합니다.
   • 2는 가장 작은 소수이므로 소인수분해는 항상 2부터 시작합니다.
3. while i <= n:
   • i가 n보다 작거나 같을 동안 반복합니다. 즉, n이 1이 될 때까지 소인수분해를 진행합니다.
4. if n % i == 0:
   • n이 i로 나누어떨어지는지 검사합니다.
   • 나누어떨어지면 i는 n의 소인수입니다.
5. print(i)
   • i가 소인수임을 출력합니다.
6. n //= i
   • n을 i로 나눈 몫으로 갱신합니다.
7. else:
   • n이 i로 나누어떨어지지 않을 때 실행됩니다. 현재 i는 n의 약수가 아닙니다.
8. i += 1
   • 다음 숫자로 넘어가 다시 나눕니다.
   • 예: 2로 다 나누었다면 3, 그다음 4 … 이런 식으로 증가합니다.